random permutations

[Dimitre Novatchev]

--- George Russell <ger@tzi.de> wrote:
> I think Ralf Hinze's method is the best presented so far.  I would
> write
> it slightly differently though.  In pseudo-code I would proceed as
> follows:
> (1) write the values to an array a[1]..a[n]
> (2) for i from n to 2
>     do
>        j <- random integer between 1 and i
>        swap a[i] and a[j]
> At the end the elements of a will be a random permutation.  In
> Haskell
> you can of course use an STArray for this.
> 
> Ralf Hinze's method requires you to do n multiplications and n
> divisions
> to compute the factorial and then compute a random number.  I have
> to compute n random numbers rather than a single random number, on
> the
> other hand I don't have to do the multiplications and divisions.
> Indeed, since you need more random bits to compute a random big
> number
> than a random little number, I don't think in theory my method
> requires
> much more work from the random number generator than Ralf Hinze's.


This is exactly how I did it in producing a randomised node-set in
XSLT:


"Randomization of node-sets or node-lists"
http://www.topxml.com/code/default.asp?p=3&id=v20020504013704





=====
Cheers,

Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL

__________________________________________________
Do you Yahoo!?
Yahoo! Tax Center - forms, calculators, tips, more
http://taxes.yahoo.com/