The imperative implementation of the algorithm is well known. Let’s arrange the input sequence (e1, e2, …en) into an array ‘a’ so that initially a[i] = ei, i=1..n. At step 1, we choose a random number r1 uniformly from [0..n-1]. Thus a[1+r1] will be the first element of the permuted sample, b1. We swap a[1+r1] and a[1]. Thus a[1] will contain b1. At step 2, we choose a random number r2 uniformly from [0..n-2]. a[2+r2] will be a uniform sample from {e1..en} – {b1}. After we swap a[2] and a[2+r2], a[2] will be b2, and a[3..n] will contain the remaining elements of the original sequence, {e1..en} – {b1,b2}. After n-1 steps, we’re done. The imperative algorithm in OCaml has been already posted on this thread.
Includes an implementation example and a critique of sort-based algorithms.
Apphacker 