# Why shuffling by picking random position in all array instead of a part is not correct

There is a famous problem to generate a random permutation of elements in an array - it's called shuffling. My understanding of that problem is that I have to put every element in an array into a random position. So for each element in an array I can generate a random position and put it there by swapping:

for (let i = 0; i < a.length; i++) {
const position = rand.nextInt(a.length);
const tmp = a[i];
a[i] = a[position];
a[position] = tmp;
}


This is almost what the improved Fisher–Yates shuffle algorithm is doing. However my solution is not correct. According to the link I need to generate numbers from the 0..i range, not from 0..length. Can anyone please explain me why it is so?

In my implementation all the numbers are still put into random positions, so what's the problem?

• It will shuffle but it will not be uniform i.e. all elements will not have an equal chance of appearing at some position 'i' Commented May 16, 2017 at 16:40

There is a simple mathematical argument that your algorithm cannot pick each permutation with equal probability: There are $n^n$ possibilities how your algorithm can choose random numbers, each with equal probability, and each producing some permutation. There are $n!$ possible permutations. But $n^n$ is not divisible by $n!$ if $n ≥ 3$, therefore the permutations cannot all be the result of the same number of random choices.

Yuval gave the example for n = 3: There are $3^3=27$ possible choices of random numbers, and $3! = 6$ possible permutations. $27/6 = 4.5$. It is not possible that each permutation is the result of 4.5 different choices of random numbers. As Yuval's table shows, there are three permutations each being produced by 4 and by 5 choices of random numbers, so some permutations must be more likely than others.

For n = 2 this argument doesn't show any problem since $2^2 = 4$ is divisible by $2! = 2$, and indeed the algorithm produces a random permutation.

• thanks a lot for your elaborate answer! I find it very helpful. Yuval's answer as I understand is also very good, but it's difficult for me to understand given my limited knowledge of the topic. Can you please clarify a few things? there are three permutations each being produced by 4 and by 5 choices of random numbers - what do you mean by produced by 4 and by 5 choices? Commented May 17, 2017 at 8:07
• therefore the permutations cannot all be the result of the same number of random choices - can you maybe provide an example? Commented May 17, 2017 at 8:08
• any comment on my questions above? Commented May 23, 2017 at 10:34

Suppose that the array has length $n$. Since you are making $n$ random choices of numbers from 1 to $n$, the probability to obtain any specific permutation is of the form $A/n^n$, for some integer $A$. Therefore your algorithm could work only if $n^n/n!$ is an integer, which is only the case when $n \leq 2$.

More concretely, if you shuffle the array $1,2,3$, then you get the following results: $$\begin{array}{c|c} \text{array} & \text{probability} \\\hline 1,2,3 & 4/27 \\ 1,3,2 & 5/27 \\ 2,1,3 & 5/27 \\ 2,3,1 & 5/27 \\ 3,1,2 & 4/27 \\ 3,2,1 & 4/27 \end{array}$$

• thanks, how do you calculate the probability 4/27 and 5/27 in your table? Commented May 17, 2017 at 8:09
• @Maximus I ran all 27 possible executions of the program. Commented May 17, 2017 at 12:16
• aha, and then what? I'm sorry I can seem to understand how you end up with the table results Commented May 17, 2017 at 15:46
• You'll have to figure this out yourself. Commented May 17, 2017 at 15:55

Well, you are putting the numbers in random positions, although this is not the correct implementation of Fisher–Yates shuffle algorithm (if you intended to). You are basically using a slightly different algorithm such that:

If n = a[i] is swapped with m = a[position], the algorithm can still generate position = i and swap m = a[i] with another number a[i+1]. In Fisher–Yates shuffle algorithm this wouldn't happen as it would use i+1 ... a.length-1 as possible values for position. So m wouldn't be swapped again.

EDIT: You should also check this question and understand the concept of uniform shuffle.

• This might help for a better understanding youtube.com/watch?v=54rMYC2pEtw Commented May 16, 2017 at 16:31
• This doesn't quite explain what goes wrong if you use the wrong algorithm. Commented May 16, 2017 at 18:02