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