Random chaos probability in Java (or any language)

See English answers > what distribution do you get from this broken random shuffle? 10

for(int i = 0; i < N; i++)
int r = new Random().nextInt(53);
swap(cardArray,i,r);

It iterates over all cards once In each iteration, a random number is generated and the I - th card is exchanged with the R - th card Is it easy?

Although I understand the algorithm, I don't understand his probability calculation He said that because random uses 32-bit seeds (or 64, it doesn't seem important), this is limited to 2 ^ 32 different permutations

He also said Knuth's algorithm is better (the loop is the same, but choose the number between 1 and I) because it gives you n! Arrange

I agree with Knuth's algorithm But I think there should be n ^ n different permutations on the first (should be wrong)

Was Sedgwick wrong or did I miss a fact?

Solution

Sedgewick's way of explaining it seems strange and dull to me

Imagine that you only have 3 cards and apply the algorithm shown

After exchanging the first card, there will be three possible results After the second, Ninth exchange, after the third exchange, 27 Therefore, we know that using the exchange algorithm, we will have 27 different possible results, some of which will be repeated results of other results

Now, we know the fact that there are 3 * 2 * 1 = 6 possible arrangements in the 3 card group However, 27 cannot be divided by 6 Therefore, we know that some arrangements will be more common than others, even without calculating what they are Therefore, the exchange algorithm will not produce equal probability in the six possibilities, that is, it will favor some arrangements

The same exact logic extends to the case of 52 cards

We can investigate which arrangements are preferred by looking at the distribution of results in the three card case. They are:

1 2 3 5 times 1 3 2 5 times 2 1 3 4 times 2 3 1 4 times 3 1 2 4 times 3 2 1 5 times

Total 27

Examining these, we note that combinations requiring 0 or 1 exchanges have more occurrences than combinations requiring 2 exchanges In general, the fewer exchanges required for the combination, the more likely it is