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