This program generates random permutation of N objects, the integers 0 through N-1. The strategy is to create an array, A, of length N containing the values 0 through N-1 in order. Then, do the following step for each index i, starting at N-1 and ending at 1: generate a random number j between 0 and i inclusive, and swap A(i) and A(j).

This algorithm is due originally to: R.A. Fisher F. Yates. Statistical tables for biological, agricultural and medical research (3rd ed.). pp. 26–27. London: Oliver & Boyd, 1948. It was popularized by Donald Knuth in The Art of Computer Programming vol 2.

val N = 5  -- size of permutation array
val ar = fillArray(Array(N), lambda(i) = i)

{- swap two refs' values -}
def swapRefs(x, y) = x? >z> x := y? >> y := z

def randomize(1) = signal
def randomize(n) =  -- Randomize array a of size n, n >= 1
 random(n) >k>
 swapRefs(ar(n-1),ar(k)) >>
 randomize(n-1)

randomize(N) >> map(let, ar) -- map(let, ar) creates a list from array ar

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-3) was last changed on 26-Dec-2008 11:20 by AdrianQuark