HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
randomwhypickingallarraypartpositionshufflinginsteadcorrect

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#75481, answer score: 9

Revisions (0)

No revisions yet.