Recursive permutations in C

Recursion tree for a permutation algorithm

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