/* Algorithm for traversing all permutations of N elements

#include<GNU_public_license.h>       ;-)

This is just a minimalistic implementation of this 
algorithm.  Feel free to make a proper  Interface
for it, make it a library-function, square a circle
or use it to brew coffee ...

   Author:   Andreas Leitgeb <avl@logic.at>
   Location of this file:
       <"http://avl.enemy.org/utils/permutations.c">

Characteristics: 
   callback for each Permutation
 ! only one swap between two subsequent Permutations
 ! element-type-independent (need not be numeric type)
   elements are always considered distinguishable 
       (even, if certain values occur more than once)
   Permutations are _NOT_ in any lexicographical order
------------------------------------------------------- */
#include<stdio.h>

/* number of elements to permute */
#define N 8

/* what to do each turn. 
   Take Care:   ! this macro is expanded twice !
*/
#define CALLBACK for(k=0;k<N;++k) printf("%d",p[k]); printf("\n"); 

/* can be any type. */
typedef int elemtype; 

/* define an array of N elements */
elemtype p[N];

/* the algorithm starts here */
void perm(int i) {int k; elemtype h;
   if (i>1) perm(i-1); else { CALLBACK }
   for(k=0;k<i;++k) {
      if (i&1) { h=p[i];p[i]=p[k];p[k]=h; }
      else     { h=p[i];p[i]=p[0];p[0]=h; }
      if (i>1) perm(i-1); else { CALLBACK }
   }
}
/* the algorithm ends here */


/* Frame program.  Adopt it for your special elemtype */
int main() { elemtype i;
  /* initialize ...   (works, because elemtype == int) */
  for (i=0;i<N;++i) p[i]=i;

  /* start traversal:
     parameter must be:  (number of elements to permute)-1 !!!!  */
  perm(N-1);

  return 0;
}