//  perms.c - Generate all permutations of an array.
//            Permutations not generated in lexicographic order.
//
//  Fred Curtis, 2002-09-13 -- http://f2.org/fred/
//
//  This code is based on some beautiful non-recursive code
//  by Phillip Paul Fuchs:
//    http://www.geocities.com/permute_it/01example.html

#include <stdio.h>

#define N 4

int main(void) {
  int p[N];
  int a[N];  // Array to be permuted -- can be any type & hold any values
  int i;
  int j;
  int tmp;

  for(i = 0; i < N; i++) {
    p[i] = i;
    a[i] = i + 1;
  }

  for (i = 1;;) {
    //  Do something with the permutation
    //
    int x;
    for(x = 0; x < N; x++) {
      printf("%d ",a[x]);
    }
    printf("\n");

    //  Find next variant
    //
    if (i >= N) {
      break;
    }

    //  Decrement p[i] and find index to swap with i
    //
    j = i % 2 * --p[i];

    //  Swap array elements i & j
    //
    tmp = a[j];
    a[j] = a[i];
    a[i] = tmp;

    //  Reset any run of zeroed p[i] and find next i
    for (i = 1; i < N && !p[i]; i++) {
      p[i] = i;
    }
  }
  return 0;
}