Path: utzoo!dciem!nrcaer!cunews!cognos!alanm
From: alanm@cognos.UUCP (Alan Myrvold)
Newsgroups: comp.lang.c
Subject: Re: need good permutaion generator in C
Message-ID: <8952@cognos.UUCP>
Date: 22 Oct 90 15:14:43 GMT
References: <11039@hubcap.clemson.edu>
Reply-To: alanm@cognos.UUCP (Alan Myrvold)
Organization: Cognos Inc., Ottawa, Canada
Lines: 86

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