## [f]izzbuzzer

### Looking for good programming challenges?

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

# The Knuth shuffle

The Knuth shuffle algorithm is an algorithm for randomly shuffling the elements of an array arr of size given a function that generates a uniformly distributed random number in time. The algorithm produces an unbiased permutation. That is, every permutation is equally likely.

for i in range(n-1,0,-1):
j = integer chosen uniformly randomly from [0,i]
swap arr[i] with arr[j]


Proof that the algorithm is unbiased
For any element , the probability that it will be shuffled into position (last position at zero based indexing) is: the probability that it gets selected when , which is .

For any element , the probability that it will be shuffled into position (second-to-last position) when is: the probability that it gets selected when , which is multiplied by the probability that it is not selected for the last position, which is , giving For any element , the probability that it will be shuffled into position (third-to-last position) when is: the probability that it gets selected when , which is multiplied by the probability that it is not selected for the last nor second-to-last position, which is , giving .

This can easily be generalised for any other position.

So we can see that for any element , the probability that it will be shuffled into the last, second-to-last, third-to-last, etc position is .