# 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.

1 2 3 |
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 .