On 11/17/07, Michael Kleber <michael.kleber@gmail.com> wrote:
WFL said:
Brain in gear now. Generate a random integer x in the interval [0, n!-1], and express x as a mixed-radix number to the sequence of bases n,n-1,...,i,...,1 [for larger n, maybe generate directly n integers in range [0, i] for each i]. There is now a simple correspondence with the x-th permutation in alphabetic order. WFL
I think the canonical implementation of this idea is to start with the identity permutation a_i=i, and then for each i=1...n swap a_i with some random a_j for i<=j<=n. That makes it really easy to see that you can get each of the n! permutations in exactly one way.
--Michael Kleber
That's a neater way to do things --- ties in nicely with Richard's excavation too! And what a pity I didn't read Nijenhuis & Wilf more carefully --- it turns out this is actually the method they (correctly) gave in 1975. [Carefully wipes egg from face.] Apart from economising on random number generations --- say by extracting [log k / log n] iterations from each integer random in [0, k-1] --- it's hard to see how this might be improved upon. So what can Akl & Meier (1984) be about, I wonder? WFL