Shuffle Algorithm: Knuth Shuffle

This post is about Knuth Shuffle, a shuffle algorithm.

- This algorithm allows random shuffle, giving all permuations of array equal likelihood.

- No need for additional arrays, so memory complexity is O(1).

- Time complexity is O(N)

 

Code is pretty simple as below.

To give all permuations of a particular array equal likelihood, all the number should have the same probability to be placed in a certain index.

So, while iterating all the indexes (i), choose a random index (j) in range [i, len(x)-1] and swap their values. Here, range of j should include i so that certain index's numbers can stay the same.

x = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def shuffle(x):
    import random
    for i in range(0, len(x)-1):
        j = random.randint(i, len(x)-1)
        x[i], x[j] = x[j], x[i]

shuffle(x)
print(x)