/* perms.c: generate all permutations of 1...n by various methods
By Terry R. McConnell
I became interested in this topic while reading Zbigniew Michalewicz and
David B. Fogel, How to Solve It: Modern Heuristics, Springer Verlag,
Berlin, 2000. As discussed in this text, generation of all permutations
is necessary, e.g., in algorithms that do exhaustive searches in the
traveling salesman problem.
It turns out there is a rather large literature on generation of
permutations, and the methods illustrated here only begin to scratch
the surface. See, e.g., R. Sedgewick, Permutation Generation Methods,
Computing Surveys, Vol. 9, No. 2, 137-164 */
/* Compile: cc -o perms -DMETHOD -DMETHODx perms.c
^^^^^^^^
see below
*/
#include
#include
#ifndef METHOD
/* Define one of METHODx x=1,2,3 depending on method selected */
#define METHOD3
#endif
#define NN 128 /* maximum allowable n. This should be big enough :-) */
static int p[NN]; /* global array to hold generated permutation */
/*
factomial: generates the "digits" in the representation of a number in
terms of factorials. Each natural number between 0 and n! - 1 has a unique
representation as a sum of terms of the form d_i*(i-1)!, where d_i lies
in the range 0..i-1, and the sum is over i=2...n.
Stores digits from least to most significant in fact_digs array, returns
the number of digits stored.
*/
static int fac_digits[NN];
int factomial(int m, int x)
{
int nfact=1,n=2,d0=0,d1,i;
for(i=0;i= 2:
n=2: to swap 1 and 2 do (1,1)(2,1). To leave them fixed do (1,1)(2,2).
Suppose n > 2. We can suppose a given permutation is cyclic, since
with relabelings the complete inductive hypothesis can be applied to
each cycle in a product of nonempty disjoint cycles. For the cyclic
permutation of 1...n-1, if we wish to insert n in the cycle at -> i
-> n -> j we can take, by induction,
[ product for case n-1 taking i->j ] (n,j)
We take s_i to be the ith factomial digit of the argument passed
in.
*/
/* Helper */
int swap(int i, int j){
int temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
return 0;
}
int gen_perm1(int n){
int i;
for(i=0;i 001 -> 002 -> 010 -> 011 -> 012
Returns 1 when the last permutation has been generated, 0 else.
N.B.: there are at least 2 typos in the psuedocode description of this
algorithm presented in the Michalewicz and Fogel book (p. 63.)
*/
static xx[NN];
int gen_perm3(int n)
{
int i;
static int first_call = 1;
if(first_call){ /* initialize */
for(i=0;i0;i--){
if(xx[i] != i)break;
xx[i] = 0;
}
if(i==0)return 1;
xx[i] = xx[i]+1;
p[0] = 1;
for(i=0;i