[comp.lang.c] need good permutaion generator in C

grimlok@hubcap.clemson.edu (Mike Percy) (10/19/90)

I'm looking for an iterative (not recursive like the ones I already
know) permutation routine -- to wit:
 
int T[] = { 1, 2, 3}   
 
for(i = 0; i < n!; i++)
{
  /* make permutation(i) of T */
  /* use permutation(i) of T */
}

the permutations of T are 
1 2 3 
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
 
I see a swap() coming into play, but I can't quite get it right. 
Also, I'm not picky about what order the permutations come out in,
just that each be generated exactly once.

"I don't know about your brain, but mine is really...bossy."
Mike Percy                    grimlok@hubcap.clemson.edu
ISD, Clemson University       mspercy@clemson.BITNET
(803)656-3780                 mspercy@clemson.clemson.edu

daveg@near.cs.caltech.edu (Dave Gillespie) (10/22/90)

>>>>> On 19 Oct 90 15:15:37 GMT, grimlok@hubcap.clemson.edu (Mike Percy) said:

> I'm looking for an iterative (not recursive like the ones I already
> know) permutation routine.

Dijkstra's _A Discipline of Programming_ has a nice little next-permutation
algorithm.  Given an input permutation in an array, it changes it to the
lexicographically next permutation.  So you start with "1 2 3" and repeat
the algorithm until you get to "3 2 1".

Dijkstra invents his own language for use in this book, but I'll be brave
and do an off-the-cuff translation to C.  (This will be untested, but
then Dijkstra proudly states in the introduction that his programs were
published untested since they were derived by such rigorous methods.
Hey, guys, let's start a flame war on the merits of that remark!)


#define SWAP(x,y) { int t = x; x = y; y = t; }

/* Increment the permutation in perm[0] ... perm[n-1]. */
void next_perm(int perm[], int n)
{
  int i = n - 2;   /* Index of leftmost element which needs to change. */
  int j = n - 1;   /* Index of element perm[i] will change to. */

  /* Only the tail of elements in decreasing order must change. */
  while (perm[i] >= perm[i+1]) i--;

  /* perm[i] inherits the next-higher value from the tail. */
  while (perm[j] <= perm[i]) j--;

  /* Swap that into position.  Rest of tail is still decreasing. */
  SWAP(perm[i], perm[j]);

  /* Now reverse the tail end-for-end to get increasing order. */
  j = n;
  while (++i < --j)
    SWAP(perm[i], perm[j]);
}


I always thought this was a fine example of the beauty of good
algorithms.  A place for everything, everything in its place.

You can get the program to test if you have reached the last
permutation automatically by changing the first while loop thusly:

  while (perm[i] >= perm[i+1])
    if (--i < 0)
      return DONE;   /* Input was already the last permutation */

								-- Dave
--
Dave Gillespie
  256-80 Caltech Pasadena CA USA 91125
  daveg@csvax.cs.caltech.edu, ...!cit-vax!daveg

alanm@cognos.UUCP (Alan Myrvold) (10/22/90)

In article <11039@hubcap.clemson.edu> grimlok@hubcap.clemson.edu (Mike Percy) writes:
>I'm looking for an iterative (not recursive like the ones I already
>know) permutation routine -- to wit:
> 
>int T[] = { 1, 2, 3}   
> 
>for(i = 0; i < n!; i++)
>{
>  /* make permutation(i) of T */
>  /* use permutation(i) of T */
>}

When I was at Red Bank High School (Tennessee) in 1980-1981 a girl named Jenny
came in and typed in an iterative permutation routine (in BASIC).  I didn't 
see the source, and it actually took a little while to come up with an 
algorithm. But here is one (translated from BASIC to C):


#include <stdio.h>

int T[] = {1,2,3};

void fact(T,n)
int T[],n;
{
   int i,j,k,l,*f,*g,*h,*q;

   /* Initialize */
   if (n < 1) return;
   f = (int *) malloc((n+1)*sizeof(int));
   g = (int *) malloc(n*sizeof(int));
   h = (int *) malloc(n*sizeof(int));
   q = (int *) malloc(n*sizeof(int));
   if (!f || !g || !h || !q) {
      fputs("Out of memory!\n",stderr);
      return;
   }
   /* Note that f[k] = k! */
   for (i = f[0] = 1; i <= n; i++) f[i] = i*f[i-1];

   /* Generate the permutations */
   for (i = 0; i < f[n]; i++) {
       /* A bit messy here, but it does the trick */
       for (k = i,j = 0; j < n; j++) {
           h[j] = 1;
           g[j] = k / f[n-j-1];
           k -= f[n-j-1]*g[j];
       }
       for (k = 0; k < n; k++) {
           for (j = l = 0; j < 1+g[k]; j+=h[l++]);
           h[q[k] = l-1] = 0;
       }

       /* Print the permutation (by indexing off q) */
       for (j = 0; j < n; j++) printf("%d ",T[q[j]]);
       printf("\n");
   }

   /* Clean up */
   free(q);
   free(h);
   free(g);
   free(f);
}

int main(argc,argv)
int argc;
char *argv[];
{
   fact(T,3);
}

Hope this helps.

>I see a swap() coming into play, but I can't quite get it right. 

No swaps above. Sorry.


                                          - Alan

---
Alan Myrvold          3755 Riverside Dr.     uunet!mitel!cunews!cognos!alanm
Cognos Incorporated   P.O. Box 9707          alanm@cognos.uucp
(613) 738-1440 x5530  Ottawa, Ontario       
                      CANADA  K1G 3Z4