This algorithm is similar to the direct insertion order permutation algorithm, except that instead of inserting a new element into the spaces between existing elements, the new element is inserted into a space already occupied by an existing element or at the end. If the space is already occupied, the existing element is bumped to the end of the permutation.

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

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) {
                /* Bump the existing element to the end */
                perm[level] = perm[i];
            }
            perm[i] = str[level];
            permutations_recursive(str, perm, level + 1, len, fun);
            if (level > 0 && i < level) {
                /* Move the existing element back */
                perm[i] = perm[level];
            }
        } 
    }
}

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

Example program:

#include <stdio.h>

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

The output:

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

Reference: Decision Trees