6 Mar
2003
6 Mar
'03
10:19 a.m.
Markus.Schnell@infineon.com wrote:
Is there a library routine for random permutations?
I didn't find any and did a quick hack...
There are many algorithms. One, quite natural and quite fast (n log n; slower than linear, though...) consists in: 1. Generate N random numbers r_k, say, uniform between 0 and 1. 2. Form N pairs (1,r_1), (2,r_2), (3, r_3) ... (N,r_n). 3. Sort this list/vector wrt the *secon* (random) number. 4. In the sorted list the firs values (indices) give you the result. This is of course quite general, not restricted to any Haskell peculiarities. Jerzy Karczmarczuk