## § 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 `i`

th location. Th index `r`

is a random index chosen in `[0, i]`

which is the element to be chosen as the value at the `i`

th location.

```
@composite
def permutation(draw, n):
xs = { i : xs[i] for i in range(n) }
i = n-1
while i >= 0:
r = draw(integers(0, i))
temp = xs[i]; xs[i] = xs[r]; xs[r] = temp;
i -= 1
return xs
```