Programming interview questions

Looking for good programming/interview questions?

Use the search below to find our solutions for selected questions!

The Knuth shuffle

Sharing is caring!

The Knuth shuffle algorithm is an algorithm for randomly shuffling the elements of an array arr of size n given a function that generates a uniformly distributed random number in \mathcal{O}(1) time. The algorithm produces an unbiased permutation. That is, every permutation is equally likely.

Proof that the algorithm is unbiased
For any element e, the probability that it will be shuffled into position n-1 (last position at zero based indexing) is: the probability that it gets selected when i=n-1, which is \frac{1}{n}.

For any element e, the probability that it will be shuffled into position n-2 (second-to-last position) when i=n-2 is: the probability that it gets selected when i=n-2, which is \frac{1}{n-1} multiplied by the probability that it is not selected for the last position, which is 1 - \frac{1}{n} = \frac{n-1}{n}, giving  \frac{1}{n-1}\times\frac{n-1}{n} = \frac{1}{n}

For any element e, the probability that it will be shuffled into position n-3 (third-to-last position) when i=n-3 is: the probability that it gets selected when i=n-3, which is \frac{1}{n-2} multiplied by the probability that it is not selected for the last nor second-to-last position, which is 1 - \frac{2}{n} = \frac{n-2}{n}, giving \frac{1}{n-2}\times\frac{n-2}{n} = \frac{1}{n}.

This can easily be generalised for any other position.

So we can see that for any element e, the probability that it will be shuffled into the last, second-to-last, third-to-last, etc position is \frac{1}{n}.