2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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' $\endgroup$ – Romantic Electron May 16 '17 at 16:40
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Maxim Koretskyi May 17 '17 at 8:07
  • $\begingroup$ therefore the permutations cannot all be the result of the same number of random choices - can you maybe provide an example? $\endgroup$ – Maxim Koretskyi May 17 '17 at 8:08
  • $\begingroup$ any comment on my questions above? $\endgroup$ – Maxim Koretskyi May 23 '17 at 10:34
7
$\begingroup$

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} $$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.