This recursive algorithm produces the permutations in the most natural order, and is also the easiest to understand. It uses two buffers, one containing the permutation being built, and another for the remaining, unused letters.
The algorithm is:
if (there are no more characters to arrange) { print (the current permutation); } else { choose a remaining character; remove it from the remaining characters; add it to the permutation; use recursion to add the remaining characters to the permutation in the same way; }
Here it is in C:
#include <stdlib.h> #include <string.h> typedef void(*permutationfn)(const char *); static void permutations_recursive(char *perm, size_t used, char *remaining, size_t len, permutationfn fun) { if (used == len) { perm[used] = '\0'; fun(perm); } else { const size_t unused = len - used; unsigned int i; for (i = 0; i < unused; i++) { /* Remove character at i from remaining */ char c = remaining[i]; memmove(remaining + i, remaining + i + 1, unused - i); /* Append it to perm */ perm[used] = c; permutations_recursive(perm, used + 1, remaining, len, fun); /* Put character back */ memmove(remaining + i + 1, remaining + i, unused - i); remaining[i] = c; } } } void permutations(const char *str, permutationfn fun) { const size_t len = strlen(str); char *perm = malloc(len + 1); char *remaining = malloc(len + 1); if (perm && remaining) { strcpy(remaining, str); permutations_recursive(perm, 0, remaining, len, fun); } free(perm); free(remaining);
Example program:
#include <stdio.h> int main(void) { char str[] = "ABCD"; permutations(str, (permutationfn)puts); return 0; }
The output:
ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA
Reference: Exhaustive recursion and backtracking