Knuth shuffle

The Knuth shuffle is a simple, elegant algorithm for randomly permuting a list. It’s not used very often, but it’s one of my favourite algorithms.

Here’s how it works: for a list n with elements n[0], n[1], …, n[N-1], pick an index uniformly distributed over 0,1,…,N-1. That index is swapped with n[0]. (If you pick index 0, the swap is trivial.) Then an index over 1,2,…,N-1 is swapped with n[1]; over 2,3,…,N-1 is swapped with n[2], and so on through the list.

Note the shuffle is recursive: after swapping n[i], the operation over n[i+1],…,n[N-1] is a Knuth shuffle.

You can show by induction that all N! possible permutations can be generated by this algorithm. For N=2, the first step leaves the list the same, or swaps n[0] and n[1]; the second step is trivial, so there are 2 = 2! possible permutations. Since the algorithm is recursive, assume the shuffle over n[1],…,n[N-1] produces (N-1)! possible permutations. There are N possible swaps of n[0] with an index in 0,1,…,N-1; thus, there are a total of N(N-1)! = N! permutations. A similar inductive argument shows that the shuffle is uniformly distributed over the permutations.

Here’s a Knuth shuffle in Python, with a few demonstration lines at the end.

import random as rnd

def shuffle(n,start=0):
    
    # base case: 
    # the only remaining element is the last one
    if (start == len(n)-2):
        return n

    # recursive case: 
    # swap n[start] with a randomly selected element 
    # from the rest of the list
    swapIndex = rnd.randint(start,len(n)-1)
    foo = n[start]
    n[start] = n[swapIndex]
    n[swapIndex] = foo
    return shuffle(n,start+1)

# demonstration
n = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
print(n)
print(shuffle(n))