A Universe of Sorts

§ 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