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))