🚀 go-pugleaf

In article <1993Jan6.014749.15323@ee.ubc.ca>, rayw@ee.ubc.ca (raymond w m woo) writes...
>Hi, does anyone know, or can provide any pointer in the literature to, any 
>random permutation generation algorithm that can be easily implemented as a 
>function in a computer program?  
> 
>Ideally, this function would be computationally effective, and the input 
>that this function takes would be some kind of index/rank number of the
>permution to be generated.  

A coset algorithm works very well for uniformly choosing an element
of a group (in this case the symmetric group.)

   initialize n element array a(i) = i

   for i = 1 to n-1
       j = random integer from i to n inclusive
       exchange a(i) and a(j)
       (it is possible that i = j and no exchange takes place above)
   end

   now a contains a random permutation of n elements

This is far nicer than approaches I've seen (such as generating a random
list of numbers, sorting them, and returning the resulting permutation!)

- Jim