• We wish to generate a random permutation.
• Assume we can generate a random permutation of $[a, b, c]$.
• How do we extend this to a random permutation of $[w, x, y, z]$?
• Idea: (0) Consider $\{w, x, y, z\}$ in a line. Our random permutation is $[\_, \_, \_, \_]$.
• (1) Decide who goes at the rightmost blank. Suppose $y$. Then our random permutation state is $[\_, \_, \_, y]$.
• (2) What do we have left? We have $\{w, x, z \}$. Use recursion to produce a random permutation of length 3 with $[w, x, z]$.
• (3) Stick the two together to get a full random permutation.
• To save space, we can write this on a "single line", keeping a stick to tell us which part is the "set", and which part is the "array":

0. {w,  x,  y, z}[]1. {w, x, y, [z}] (growing array)1. {w,  x,  z, [y}] (swapping z<->y)<->1. {w,  x,  z}, [y] (shrinking set)

Similarly, for the next round, we choose to swap w with z as follows:

1. {w,  x,  z}, [y]2. {w, x,  [z}, y] (grow array)2. {x,  z, [w}, y]  (swap w <-> x)<->2. {x, z}, [w, y] (shrinking set)

For the next round, we swap z with z (ie, no change!)

2. {x,  z}, [w, y]3. {x, [z}, w, y] (grow array)3. {x, [z}, w, y] (swap z<->z)<->3. {x},[z, w, y] (shrink set)

Finally, we swap x with x:

3. {x},  [z, w, y]4. {[x}, z, w, y] (grow array)3. {x}, [z, w, y] (swap x<->x)<->3. {}[x, z, w, y] (shrink set)

• This way, we generate a random permutation in place , by treating the left portion of the sequence as a set, and the right portion of the sequence as a sorted permutation. At each stage, we grow the array, and choose a random element from the set to "enter" into the array at the location of intersection between set and array.

• In code, the index i tracks the location of the array border, where we must fix the value of the permutation (ie, the ordering of elements) at the ith location. Th index r is a random index chosen in [0, i] which is the element to be chosen as the value at the ith location.

@compositedef permutation(draw, n):    # raw random    # Fishes Yates: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle    xs = { i : xs[i] for i in range(n) }    i = n-1 # from (n-1), down to zero.    while i >= 0:        r = draw(integers(0, i)) # r ∈ [0, i]        temp = xs[i]; xs[i] = xs[r]; xs[r] = temp; # swap        i -= 1    return xs