| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1365.1 | | GUESS::DERAMO | Dan D'Eramo | Fri Jan 04 1991 14:01 | 6 |
| It looks like you are using an explicit bijective
correspondence between {1,...,n!} and the permutation
group on n objects. Just loop from 1 to n! and print out
the "decoding" of the loop index variable.
Dan
|
| 1365.2 | | HANNAH::OSMAN | see HANNAH::IGLOO$:[OSMAN]ERIC.VT240 | Fri Jan 04 1991 14:13 | 5 |
|
Even if the decoding is unique, it doesn't prove that the permuations are
unique, since we must prove that whenever two decodings differ, their resultant
permuations differ also.
|
| 1365.3 | Another approach | CIVAGE::LYNN | Lynn Yarbrough @WNP DTN 427-5663 | Fri Jan 04 1991 17:02 | 9 |
| There are several nice algorithms to do this. One of the best is NEXPER in
Nijenhuis & Wilf's *Combinatorial Algorithms*, which generates them one at
a time by interchanging two object indices, which has the effect of
minimizing the amount of object movement. I have a nice structured FORTRAN
version of this if you need it.
No, it does not vectorize well!
Lynn
|
| 1365.4 | | GUESS::DERAMO | Dan D'Eramo | Fri Jan 04 1991 17:48 | 9 |
| The Knuth section on random number generation discusses
encoding a permutation as a number from 1 to n! It's
kind of a base 2-3-4-...-n (or was it n-...-4-3-2?)
notation. It's not as useful to run through every
permutation as the simpler "next permutation" generators
are, but it gives you "random access" to the k-th
permutation.
Dan
|
| 1365.5 | YAP (Yet Another Permutation-algorithm) | UTRUST::DEHARTOG | moduladaplisprologopsimulalgol | Mon Jan 07 1991 04:54 | 20 |
| Years ago I also needed the permutation of a given string of characters.
Here follows the code. For every string it reads (until EOF), it prints
all permutations starting with the string itself and ending with the
reversed string.
#include <stdio.h>
#define ML 100
int L; char A[ML], B[ML];
main(){
while(gets(A)){
for(L=0;L<ML;L++) B[L]='\0'; L=strlen(A); perm(A);
}
}
perm(S) char *S; {
int j;
for(j=0;j<L;j++) if(!B[j]){
B[j] = *S; if(S[1]) perm(S+1); else puts(B); B[j]='\0';
}
}
|
| 1365.6 | | CIVAGE::LYNN | Lynn Yarbrough @WNP DTN 427-5663 | Mon Jan 07 1991 11:16 | 3 |
| [.5] This is the simple lexical-order recursion algorithm, which is very
clean but, I think, does more than the minimum data movement. For example,
when racheting from [15432] to [21345] everything moves.
|