Re: Generating "next permutation"
- From: Proginoskes <CCHeckman@xxxxxxxxx>
- Date: Wed, 01 Aug 2007 03:12:41 -0000
On Jul 31, 6:52 pm, Knight <knightt...@xxxxxxxxx> wrote:
Hi,
you are given an ordered set, say, 1 2 3 4 5. You are required to
generate permutations which are strictly numerically increasing, i.e.
in the order
12345
12354
12435
12453
12534
12543
13245
13254
13425
13452
13524
....
AKA "lexigraphically ordered".
Now if I tell you that I've generated these permutations upto the N'th
one, e.g. upto 35214, can you guess the "N+1"th (or "N+1"st, whatever)
"quickly"? In this case the answer is 35241.
"Quickly" is a vague term, but I do mean "without generating all
permutations from 1st to N+1st".
You only need the Nth permutation, actually.
One way to do this is to subtract 1 from each of the digits, to get a
5-"digit" base-5 number. Now add 1 repeatedly until you get a new
number in base 5 where all the "digits" are distinct. Then add 1 to
each digit, and that's your permutation.
You can also generate an arbitrary permutation, only knowing which
position it's in; hence you would only need to know N+1. I posted C
code in the thread "Generating N! permutation" in sci.math about a
year ago, to go from position to permutation, and vice versa:
You can also convert from the permutation to its position, or vice
versa. Thus, you can generate all permutations by asking for
permutation #1, #2, ..., #(N!). In C, this is how I did it (using
macros):
#define prm2lex(X,Y) X = 1; \
for (ii = n; ii; ii --) b [ii] = 1; \
for (ii = 1; ii < n; ii ++) { \
for (jj = Y [ii], kk = -1; jj ; kk += b [jj], jj --); \
X += fact [n - ii] * kk;
This line means: X := X + fact [n - ii] * kk.
b [Y [ii]] = 0; }
#define lex2prm(X,Y) xp = X - 1; \
for (ii = n; ii ; ii --) b [ii] = 1; \
for (ii = 1; ii < n; ii ++) { \
kk = xp / fact [n - ii]; \
xp %= fact [n - ii]; \
This line means: xp := xp MOD fact [n - ii].
for (jj = 1; kk ; jj ++) if (b [jj]) kk --; \
while (!b [jj]) jj ++; \
Y [ii] = jj; b [jj] = 0; } \
for (jj = n; !b [jj]; jj --); Y [n] = jj;
prm2lex(X,Y) will convert a permutation (in the array Y) into its
position (between 1 and n!), and lex2prm(X,Y) will find the Xth
permutation and put it into the array Y (X between 1 and n!). Here,
fact [k] = k!.
The rest of the macros should be self-explanatory. The only downside
here is that n can't be too big.
--- Christopher Heckman
.
- References:
- Generating "next permutation"
- From: Knight
- Generating "next permutation"
- Prev by Date: Re: Still wanting help with solving this FLT
- Next by Date: Re: Why wrappers? Example with the why.
- Previous by thread: Re: Generating "next permutation"
- Next by thread: Re: Generating "next permutation"
- Index(es):
Relevant Pages
|
