Heap's algorithm for iterating over permutations of n

permute.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool print_permutation(unsigned int n,
                       unsigned int permutation[n],
                       unsigned int count[n]) {
  printf("Permutation: [");
  for (unsigned int i = 0; i < n; i++) {
    printf(" %u", permutation[i]);
  }
  printf(" ]; Factoradic index: (");
  for (unsigned int i = 0; i < n; i++) {
    printf(" %u", count[i]);
  }
  printf(" )\n");
  return false; // hit all the permutations
}

void search_permutations (unsigned int n,
                          bool (*test)(unsigned int,
                                       unsigned int[],
                                       unsigned int[])) {
  // The current permutation, as a list of numbers from 0 to n-1, of
  // length n, where permutation[i] == j indicates that i is sent to j
  // by the permutation.
  unsigned int permutation[n]; // the current permutation
  for (unsigned int i = 0; i < n; i++) {
    permutation[i] = i;
  }

  // The factoradic index of the current permutation (this mimics the
  // list of loop counters in the frames on the stack that you would
  // have in the recursive version of this)
  unsigned int count[n];
  memset(count, 0, sizeof(unsigned int) * n);

  // start at the beginning of the deepest nested loop in the
  // recursion
  for (unsigned int right = 1;;) {

    // loop body (done once per permutation)
    if (test(n, permutation, count)) {
      // do whatever needs to be done when you find what you're
      // looking for
      return;
    }

    // find the next permutation, if any

    // back out however many levels of recursion necessary to find the
    // next loop iteration, if any
    while (count[right] == right) {
      count[right] = 0;
      right++;
    }
    if (right >= n) break;

    // perform the swap that generates the next permutation
    unsigned int left = (right % 2) * count[right];
    unsigned int tmp = permutation[left];
    permutation[left] = permutation[right];
    permutation[right] = tmp;

    // increment the factoradic index
    count[right]++;
    right = 1;
  }
}

int main (int argc, char** argv) {
  if (argc != 2) {
    fprintf(stderr, "Usage: permute <n>\n");
    return 1;
  }
  unsigned int n = atoi(argv[1]);

  search_permutations(n, print_permutation);

  return 0;
}

results.txt

$ ./permute 4
Permutation: [ 0 1 2 3 ]; Factoradic index: ( 0 0 0 0 )
Permutation: [ 1 0 2 3 ]; Factoradic index: ( 0 1 0 0 )
Permutation: [ 2 0 1 3 ]; Factoradic index: ( 0 0 1 0 )
Permutation: [ 0 2 1 3 ]; Factoradic index: ( 0 1 1 0 )
Permutation: [ 1 2 0 3 ]; Factoradic index: ( 0 0 2 0 )
Permutation: [ 2 1 0 3 ]; Factoradic index: ( 0 1 2 0 )
Permutation: [ 3 1 0 2 ]; Factoradic index: ( 0 0 0 1 )
Permutation: [ 1 3 0 2 ]; Factoradic index: ( 0 1 0 1 )
Permutation: [ 0 3 1 2 ]; Factoradic index: ( 0 0 1 1 )
Permutation: [ 3 0 1 2 ]; Factoradic index: ( 0 1 1 1 )
Permutation: [ 1 0 3 2 ]; Factoradic index: ( 0 0 2 1 )
Permutation: [ 0 1 3 2 ]; Factoradic index: ( 0 1 2 1 )
Permutation: [ 0 2 3 1 ]; Factoradic index: ( 0 0 0 2 )
Permutation: [ 2 0 3 1 ]; Factoradic index: ( 0 1 0 2 )
Permutation: [ 3 0 2 1 ]; Factoradic index: ( 0 0 1 2 )
Permutation: [ 0 3 2 1 ]; Factoradic index: ( 0 1 1 2 )
Permutation: [ 2 3 0 1 ]; Factoradic index: ( 0 0 2 2 )
Permutation: [ 3 2 0 1 ]; Factoradic index: ( 0 1 2 2 )
Permutation: [ 3 2 1 0 ]; Factoradic index: ( 0 0 0 3 )
Permutation: [ 2 3 1 0 ]; Factoradic index: ( 0 1 0 3 )
Permutation: [ 1 3 2 0 ]; Factoradic index: ( 0 0 1 3 )
Permutation: [ 3 1 2 0 ]; Factoradic index: ( 0 1 1 3 )
Permutation: [ 2 1 3 0 ]; Factoradic index: ( 0 0 2 3 )
Permutation: [ 1 2 3 0 ]; Factoradic index: ( 0 1 2 3 )
$ for x in $(seq 0 10) ; do time ./permute $x > /dev/null ; done |& grep user | awk '{print i++, $0}'
0 user	0m0.000s
1 user	0m0.000s
2 user	0m0.000s
3 user	0m0.000s
4 user	0m0.000s
5 user	0m0.000s
6 user	0m0.000s
7 user	0m0.012s
8 user	0m0.084s
9 user	0m0.548s
10 user	0m5.892s
$ for x in $(seq 0 10) ; do ./permute $x | wc -l ; done | awk '{print i++, $0}'
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
$