Xref: utzoo comp.theory:577 sci.math:10665
Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!ogicse!dali!uakari.primate.wisc.edu!uflorida!haven!decuac!e2big.dec.com!shlump.nac.dec.com!jareth.enet.dec.com!edp
From: edp@jareth.enet.dec.com (Always mount a scratch monkey.)
Newsgroups: comp.theory,sci.math
Subject: Re: efficient algorithm for generating permuations
Message-ID: <10270@shlump.nac.dec.com>
Date: 13 Apr 90 18:00:22 GMT
Sender: newsdaemon@shlump.nac.dec.com
Followup-To: comp.theory
Organization: Digital Equipment Corporation
Lines: 35

In article <Apr.13.10.59.00.1990.217@straits.rutgers.edu>,
majidi@straits.rutgers.edu (Masoud Majidi) writes...

>Is there an easily computable function which defines a bijection from
>numbers 1..n! to permuations of 1..n

I will describe such a function.  It uses a number of division/remainder
operations, but it does what you ask for above fairly easily.  However, if you
want to generate sequences of permutations, not just one, then there are better
algorithsm, such as one that generates each possible permutation by exchange
only a single pair at a time.

I will use 0 as a base, not 1 as you have above.
Let the elements to permute be denoted with 0 to n-1.
Let k = a number from 0 to n!-1.
Let p denote the permutation we will build.  p(0) is the element the
permutation maps 0 to, 1 maps to p(1), et cetera.
Initially, set p(i) = i for all i from 0 to n-1.

Do for m ranging from n down to 2:
	Set q equal to the quotient when k is divided by m.
	Set r equal to the remainder when k is divided by m.
	Swap p(r) with p(m-1).
	Set k equal to q.

Note that if you want to generate a random permutation, forget about using k
above, omit the steps of setting q and k, and replace the step of setting r
with:

	Set r to a random integer from 0 to m-1, inclusive.


				-- edp (Eric Postpischil)
				"Always mount a scratch monkey."
				edp@jareth.enet.dec.com