Lecture 10 - Notes
February 4, 2016
Random Permutations
How do we generate a random permutation?
We would like it to be uniform with an equal probability of $\frac{1}{n!}$ for each permutation.
a = [0,1,2,...,n]
for i = n-1, i > 0, --i
t = a[i]
j = rand(0,i-1)
a[i] = a[j]
a[j] = t
we swap elements on one of the remaining elements in the list, e.g.
a = [1,2,3,4,5]
= [5,2,3,4,1]
* ^
= [5,2,4,3,1]
* ^
= [4,2,5,3,1]
* ^
= [2,4,5,3,1]
* ^
we can see this is uniform