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