Another permutation algorithm in C, this time using recursion. I got this algorithm from Eitan Gurari’s CIS 680 lecture notes, which sadly are no longer online, although they are available on the Wayback Machine here: CIS 680: DATA STRUCTURES. I’ve stolen the image above, which shows a partial recursion tree, from him.

Here is the implementation:

#include <string.h> typedef void (*permutationfn)(const char *); static void swap(char *a, char *b) { char temp = *a; *a = *b; *b = temp; } static void permutations_recursive(char *str, unsigned int left, unsigned int right, permutationfn fun) { if (left == right) { fun(str); } else { unsigned int i; for (i = left; i <= right; i++) { swap(str + left, str + i); permutations_recursive(str, left + 1, right, fun); swap(str + left, str + i); } } } void permutations(char *str, permutationfn fun) { permutations_recursive(str, 0, strlen(str) - 1, fun); }

Example program:

#include <stdio.h> int main(void) { char str[] = "ABCD"; permutations(str, (permutationfn)puts); return 0; }

The output:

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