Permutations in direct insertion order in C

To form a permutation in direct insertion order, we take an existing partial permutation containing \(k\) elements, and then insert the next element into each of the \(k+1\) possible places immediately before an element or at the end. So for example if we start with the permutation “A”, we can insert “B” before the “A” or at the end, producing “BA” and “AB”. Taking “BA”, we can then insert “C” at the beginning, between the “B” and the “A”, or at the end, producing “CBA”, “BCA”, “BAC”. The process continues until every element has been added.

Below is an implementation in C. I used a recursive function that takes a callback to process each permutation as it is found. Notice the use of memmove() to move existing elements out of the way, and then to move them back after the recursive call. We can’t use memcpy() for this, because the source and destination ranges overlap.

typedef void(*permutationfn)(const char *);

static void permutations_recursive(const char *str, char *perm, unsigned int level, size_t len, 
        permutationfn fun)
{
    if (level == len) {
        perm[level] = '\0';
        fun(perm);
    }
    else {
        /* Insert character str[level] in every position */
        unsigned int i;
        for (i = 0; i <= level; i++) {
            if (level > 0 && i < level) {
                /* Move the existing elements out of the way */
                memmove(perm + i + 1, perm + i, level - i);
            }
            perm[i] = str[level];
            permutations_recursive(str, perm, level + 1, len, fun);
            if (level > 0 && i < level) {
                /* Move the existing elements back */
                memmove(perm + i, perm + i + 1, len - i);
            }
        } 
    }
}

void permutations(const char *str, permutationfn fun)
{
    char *perm = malloc(strlen(str) + 1);
    permutations_recursive(str, perm, 0, strlen(str), fun);
    free(perm);
}

An example program:

int main(void)
{
    char str[] = "ABCD";
    permutations(str, (permutationfn)puts);
    return 0;
}

The output:

DCBA
CDBA
CBDA
CBAD
DBCA
BDCA
BCDA
BCAD
DBAC
BDAC
BADC
BACD
DCAB
CDAB
CADB
CABD
DACB
ADCB
ACDB
ACBD
DABC
ADBC
ABDC
ABCD

Reference: Decision Trees