//  perm-class.cc - 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>

class perm_loop {
private:
  int const n;
  int *p;
  int curr;
public:
  bool swap_indices(int &i, int &j) {
    if (curr >= n) {
      return false;
    }

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

    //  Reset any run of zeroed p[i] and find next curr
    for (curr = 1; curr < n && !p[curr]; curr++) {
      p[curr] = curr;
    }
    return true;
  }
  void reset() {
    for(int i = 0; i < n; i++) {
      p[i] = i;
    }
    curr = 1;
  }
  perm_loop(int const _n) : n(_n), p(new int[n]) {
    reset();
  }
  ~perm_loop() {
    delete p;
  }
};

int main(void) {
  int const N = 4;

  perm_loop ploop(N);

  int a[N];  // Array to be permuted -- can be any type & hold any values
  for(int i = 0; i < N; i++) {
    a[i] = i + 1;
  }

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

    int i;
    int j;
    if (!ploop.swap_indices(i, j)) {
      break;
    }

    //  Swap array elements i & j
    //
    int tmp = a[j];
    a[j] = a[i];
    a[i] = tmp;
  }
  return 0;
}