Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Selecting the Rth Permutation for N! pemutations

6 views
Skip to first unread message

Andrew Lee

unread,
May 25, 2001, 6:42:01 PM5/25/01
to
Hi folks,

I am grateful for any insight for this coding problem of mine's

Given a sequence of N numbers with N! possible permutations.
Assuming the members of the set of all permutations are ordered in some way
and indexed by
integers 1, 2,...,N!-1, N!.

Is there an algorithm that can select say the Rth permutation from this
ordered list without
generating all N! members of the list and storing them in an array and just
selecting the Rth row.

What would this ordering or arrangement be to effect the above indexing of
permutations and avoid
the storage of all permutations.


I expect it might be something quite trivial ot I have missed something
simple.
Any help on this is appreciated.

Cheers,

Andy


Sally Evans

unread,
May 26, 2001, 2:40:46 PM5/26/01
to
I produced something that will produce a permutation of numbers in matlab.

it will produce a permutation of n numbers, intergers 1-n

I based in on taking numbered balls out of a bag works for me

Sally


"Andrew Lee" <daz9llbbh1001@SPAM_IS_BADsneakemail.com> wrote in message
news:qcBP6.2323$Tj4.6...@news2-win.server.ntlworld.com...

Dima Pasechnik

unread,
May 28, 2001, 4:06:01 AM5/28/01
to
"Andrew Lee" <daz9llbbh1001@SPAM_IS_BADsneakemail.com> writes:

Encode permutations as maps (as opposed to cycles), e.g., with N=4,
3241 encodes (2)(134), etc.

Order them lexicografically, just like words in dictionaries are.

Observe that then you have a natural partition of N! permutations
into N classes (of size (N-1)! each),
so that the permutations with i in the 1st position
belong to i-th class. (note that knowing R, you can easily compute
where in these N classes your R-th permutation lies)

In turn, each of these classes could be partitioned into N-1 subclasses,
according to what you have in 2nd position...
Etc...

This is easy to turn into an efficient algorithm.


--
Dmitrii V. Pasechnik e-mail: d.pas...@its.tudelft.nl
ISA, TWI/ITS office location:
TU Delft HB 07.070
Postbus 5031 Mekelweg 4
2600 GA Delft 2628 CD Delft
The Netherlands phone: +31-(0)15-2787260
fax: +31-(0)15-2786632
http://ssor.twi.tudelft.nl/~dima

Andrew Lee

unread,
May 28, 2001, 7:32:16 AM5/28/01
to
Hi folks,

Thanks for the solutions to my permutation referencing problem.
I also found a paper that matches exactly what I'm looking for,
courtesy of intensive Google searches:

Ranking and Unranking Permutations in Linear Time,
Information Processing Letters, April 2000
http://www.csr.uvic.ca/~fruskey/Publications/RankPerm.html

Pretty good stuff and starting to code this up :-)

Cheers,

Andy

Lutz Tautenhahn

unread,
Jun 1, 2001, 11:35:02 AM6/1/01
to
Hi Andy,
your problem caused me to code a little script.
If the algorithm at
http://www.csr.uvic.ca/~fruskey/Publications/RankPerm.html
is too sophisticated for you , then take this one from the JavaScript in
http://www.tu-chemnitz.de/~luta/plt/PermRank.html
which is of O(n), too.
Regards, Lutz.


0 new messages