Am Samstag, 14. Februar 2009 16:37 schrieb Heinrich Apfelmus:

That of course begs the question whether there is a faster but purely

No, it didn't beg any question. (Sorry for being a humourless pedant here)

functional algorithm for generating random permutations without indexes and arrays?

The answer is a resounding "yes" and the main idea is that shuffling a list is *essentially the same* as sorting a list; the minor difference being that the former chooses a permutation at random while the latter chooses a very particular permutation, namely the one that sorts the input.

For the full exposition, see

http://apfelmus.nfshost.com/random-permutations.html

Excellent work, thanks.

Regards, apfelmus

Cheers, Daniel