§ Fisher Yates

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