Re: quick algorithm for random permutation

Ben Pfaff <blp@xxxxxxxxxxxxxxx> wrote:
John <john@xxxxxxxxxxxxxxxxxxxxxxxxxx> writes:

I need a "quick" algorithm to generate a random permutation
of 1...n. Quick means that for n=32000 or thereabouts,
it should be able to run a few hundred times on a p4-class
machine in a few seconds (i.e., before users start fidgeting).

Here's an efficient shuffle implementation in C:
http://benpfaff.org/writings/clc/shuffle.html

Thanks, again, Ben, and everyone else who replied.
This algorithm works great, was easy as pie to implement,
and runs as fast as a bat out of heck. So my problem's
solved.

But one additional "aesthetic" issue presented itself.
As is typical, I'm using the generated permutation of 1...n
to permute another array of objects. But this algorithm
can permute the objects directly, without first explicitly
generating the 1...n permutation and then applying it to
the array. So that's what I'd obviously prefer to do.

However, later on, I have to apply the inverse permutation
(unscramble the egg, so to speak). At this later point
the random number generator is pumped to exactly the same
spot, so the original sequence of (pseudo) random numbers
is reproduced. And if I explicitly generate the 1...n
permutation, it's easy to just read off the inverse.

But, is there a way to directly "inversely permute" the
permuted array of objects. For example, note that
Mike Robson's post discusses the same algorithm, but
loops from n-1...0 instead of 0...n-1. This doesn't
seem to be the inverse permutation as far as I can tell,
but is there some such modification of the original
algorithm that is the inverse?

Again, this is mostly an intellectual curiosity/aesthetic
question, as the program's running just fine as is.
But I'd gladly spend a little more time to gild its lily
if that's possible. Thanks so much for all your previous
help, and for any further ideas about this,
--
John Forkosh ( mailto: j@xxxxx where j=john and f=forkosh )
.

Relevant Pages

  • Re: Modular Algebra: Find number of elements of a subset modulo n
    ... -How to find the permutation that maps the elements of to the ... Find the multiplicative inverse of r modulo n to get the ... inverse permutation is multiplication by 29. ... are below or above a certain threshold. ...
    (sci.math)
  • Simple Permutation Game
    ... Each player writes his/her permutation in a list. ... Next the player writes the inverse permutation of their original ... Looking at the second integers in both lists, ...
    (rec.puzzles)
  • Re: some questions about A
    ... = R'*Rwhere P is a permutation matrix generated by amd, ... if one wanted the inverse permutation. ... For the dense case, I think ...
    (comp.soft-sys.matlab)
  • Simple Permutation Game
    ... Each player writes his/her permutation in a list. ... Next the player writes the inverse permutation of their original ... Looking at the second integers in both lists, ...
    (sci.math)
  • Some PERL code for detecting/displaying "toroidal" trees "invariant under a half-turn
    ... This algorithm will be reviewed by Dr. David Wagner ... Such trees can be termed "invariant" under a half-turn ... not display "the same" oDAG as the first, ... and detects whether this permutation will yield a tree ...
    (sci.math.num-analysis)