🚀 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.  

How about the following (I am trying to generate all permutations of the
integers 1, ..., N):

Start with an array v[1..N] with v[i]=i for each i.  The input is an
integer k from 1 to N! (N factorial).  Set t=N (highest entry in v)
and p=0 (first open slot in output array w[1..N]).

Now for b = N down to 2, take i = k mod b.  Copy v[i] to w[p],
increment p, copy v[t] to v[i], decrement t.  Essentially this has
just removed the i-th element of v, adding it to the output and
shrinking v accordingly.

When this is done there will be only one unused element left in v, at
v[1].  Copy it to w[N].

The running time of this algorithm should be approximately
proportional to N.

This should produce all N! possible orderings of the integers 1,...,N,
and any input in the legal range produces a unique permutation.  If
you like you can replace the integers 1 to N in array v with some
other data that you wish to permute, but the permutations will be
unique only if your data contains no duplicates.

-- David Karr (karr@cs.cornell.edu)