Permutations

[michael harrington]

Say we have ABCDEFG = 1st permutation
ABCDEGF = 2nd permutation
...etc etc
AFGBCDE = nth permutation

Anyone know how to compute n without having
to cycle through by brute force??
TIA. Mick.

[Bruce Weaver]

Take a look here:

http://mathforum.org/dr.math/faq/faq.comb.perm.html

Cheers,
--
Bruce Weaver
E-mail: wea...@mcmaster.ca
Homepage: http://www.angelfire.com/wv/bwhomedir/

[Scott Hemphill]

"michael harrington" <mik...@bigpond.com> writes:

1. Replace each letter (except the last) with the count of the
alphabetically earlier letters which occur to its right:

A F G B C D E
0 4 4 0 0 0

2. The permuation number is this sequence, taken in "factorial radix". To
convert to decimal, multiply each digit by its position value, and add the
produects. The right most digit is the 1's place, the next digit to the
left is the 2's place, the next is the 6's place, then 24's, etc.

A F G B C D E
0 4 4 0 0 0
x720 x120 x24 x6 x2 x1
---- ---- ---- ---- ---- ----
0 +480 +96 +0 +0 +0 = 576

3. This procedure gives zero for the 1st permuation, so if you want to
assign the number one to the 1st permutation, you will have to add one
to the result.

AFGBCDE = nth permutation => n = 576+1 = 577

Scott
--
Scott Hemphill hemp...@alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear

[michael harrington]

Thanks Scott. Works perfectly.
Cheers Mick.

"Scott Hemphill" <hemp...@hemphills.net> wrote in message
news:m3adqpz...@pearl.local...