## § Fisher Yates

• 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.
@composite
def 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