Skip navigation

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: