permutations.c

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

typedef int bool;
#define true 1
#define false 0

#define SWAP(a,b)       { (a) ^= (b); (b) ^= (a); (a) ^= (b); }

/* Modify the array |ap| so that it becomes the next permutation in
 * a lexicographically sorted list of all permutations of the elements
 * in |ap|. This even works if |ap| has duplicate elements.
 * Return false if |ap| is not the last permutation in the list. */
bool next_permutation(int *ap, int n)
{
    int i;
    int suffix_length = n;

    /* Find the longest non-increasing suffix. */
    for (i = 1; i < n; i++) {
        if (ap[i] < ap[i - 1]) {
            suffix_length = i;
            break;
        }
    }

    /* The entire array is non-increasing. That means that the permutation
     * has no greater successor. In other words, there is no leading
     * element. */
    if (suffix_length == n) {
        return true;
    }

    /* Reverse the suffix. */
    for (i = 0; (i + i + 1) < suffix_length; i++) {
        SWAP(ap[i], ap[suffix_length - i - 1]);
    }

    /* Find the element in the suffix to swap with leading element. It must 
     * be the smallest element that is greater than the leading element and 
     * has the highest index. */
    int swap_index = 0;
    for (i = 1; i < suffix_length; i++) {
        if (ap[swap_index] >= ap[i] && ap[i] > ap[suffix_length]) {
            swap_index = i;
        }
    }

    /* Update the leading element. */
    SWAP(ap[swap_index], ap[suffix_length]);

    return false;
}

    /* Print the array with the most significant element on the left. */
void print_permutation(const int *ap, int n)
{
    int i;
    for (i = n - 1; i >= 0; i--) {
        printf("%d%c", ap[i], i > 0 ? ' ' : '\n');
    }

}

/* Compare two permutations. The sign of the return value is 
 * the sign of the comparison. */
int compare_permutations(const int *ap, const int *bp, int n)
{
    int i;
    for (i = n - 1; i >= 0; i--) {
        if (ap[i] != bp[i]) {
            return (ap[i] > bp[i]) - (ap[i] < bp[i]);
        }
    }
    return 0;
}

int main()
{
    int n = 12;
    int i;
    int *ap;
    int *bp;
    int count = 0;

    ap = (int *) malloc(sizeof(int) * n);
    bp = (int *) malloc(sizeof(int) * n);

    /* Initialize the array to contain the least permutation 
     * according to lexicographic ordering. */
    for (i = 0; i < n; i++) {
        ap[i] = n - i - 1;
    }

    bool done;
    do {
        /* Copy the permutation for the comparison. */
        for (i = 0; i < n; i++) {
            bp[i] = ap[i];
        }
        print_permutation(ap, n);

        done = next_permutation(ap, n);

        /* Determine if the updated permutation is out of order. */
        if (!done) {
            if (compare_permutations(ap, bp, n) <= 0) {
                printf("The following permutations are out of order:\n");
                print_permutation(ap, n);
                print_permutation(bp, n);
            }
        }

        count++;
    }
    while (!done);

    printf("There were a total of %d permutations of %d elements.\n",
           count, n);

    free(bp);
    free(ap);

    return 0;
}