# 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, n, …, n[N-1], pick an index uniformly distributed over 0,1,…,N-1. That index is swapped with n. (If you pick index 0, the swap is trivial.) Then an index over 1,2,…,N-1 is swapped with n; over 2,3,…,N-1 is swapped with n, 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 and n; the second step is trivial, so there are 2 = 2! possible permutations. Since the algorithm is recursive, assume the shuffle over n,…,n[N-1] produces (N-1)! possible permutations. There are N possible swaps of n 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))