Tag Archives: Permutations

Permutation cycles in C

A cycle of a permutation is a subset of the elements that replace one another in sequence, until the last element is replaced by the first. For example, consider the permutation below:

\(\sigma=\begin{pmatrix}
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
1 & 3 & 7 & 0 & 4 & 8 & 2 & 6 & 5\end{pmatrix}\)

We can find the cycles:
\(0 \rightarrow 1, 1 \rightarrow 3, 3 \rightarrow 0\)
\(2 \rightarrow 7, 7 \rightarrow 6, 6 \rightarrow 2\)
\(4 \rightarrow 4\)
\(5 \rightarrow 8, 8 \rightarrow 5\)

These can be written as:
\((0, 1, 3)(2, 7, 6)(4)(5, 8)\)

It’s customary to omit cycles of length 1, so this would usually be written as
\((0, 1, 3)(2, 7, 6)(5, 8).\)

To find the cycle decomposition of a permutation, we can use an algorithm that is very similar to depth-first search (DFS) on a graph. We begin a new search for each unvisited vertex (number), and visit its neighbour (image in the permutation) until we get back to the first vertex again.

Below is an implementation in C. The function permutation_cycles() takes a permutation in the form of integers starting from 0, its length, and a callback function that is called for each cycle found.

#include <stdlib.h>

typedef void(*cyclefn)(const unsigned int *, size_t);

void permutation_cycles_recursive(const unsigned int *permutation, unsigned int *visited, 
        unsigned int start, unsigned int current, unsigned int *path,
        size_t length, cyclefn fun)
{
    visited[current] = 1;
    path[length] = current;
    if (start == current && length > 0) {
        fun(path, length);
    }
    else {
        permutation_cycles_recursive(permutation, visited, start, permutation[current],
                path, length + 1, fun);
    }
}

void permutation_cycles(const unsigned int *permutation, size_t n, cyclefn fun)
{
    unsigned int i;
    unsigned int *visited = calloc(n, sizeof(unsigned int));
    unsigned int *path = malloc(n * sizeof(unsigned int));
    if (!(visited && path)) {
        free(visited);
        free(path);
        return;
    }
    for (i = 0; i < n; i++) {
        if (!visited[i]) {
            permutation_cycles_recursive(permutation, visited, i, i, 
                    path, 0, fun);
        }
    }
    free(visited);
    free(path);
}

Here is an example program that finds the cycle decomposition of the permutation shown above:

#include <stdio.h>

void print(const unsigned int *cycle, size_t length)
{
    if (length > 1) {
        unsigned int i;
        putchar('(');
        for (i = 0; i < length; i++) {
            printf("%u", cycle[i]);
            if (i < length - 1) {
                printf(", ");
            }
        }
        putchar(')');
    }
}

int main(void)
{
    unsigned int permutation[] = {1, 3, 7, 0, 4, 8, 2, 6, 5};
    const size_t n = sizeof(permutation) / sizeof(permutation[0]);
    permutation_cycles(permutation, n, print);
    putchar('\n');
    return 0;
}

The output:

(0, 1, 3)(2, 7, 6)(5, 8)

Permutations in lexicographic order in C

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

Permutations in transposition order in C

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

Permutations in direct insertion order in C

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

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

Permutations

The permutations of a set are the ways of arranging its elements.

For example, there are 24 permutations of a set of 4 elements:

[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 1, 2]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 0, 2]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 2, 0, 1]
[3, 2, 1, 0]

To find the next permutation of an array ar:

  1. Find the highest index, i1 such that ar[i1] is the first of a pair of elements in ascending order.
    If there isn’t one, the sequence is the highest permutation, so reverse the whole thing to begin again.

  2. Find the highest index i2, such that i2 > i1 and ar[i2] > ar[i1].
  3. Swap ar[i1] and ar[i2].
  4. The elements from ar[i1 + 1] to the end are now in descending order (a later permutation), so reverse them.
static void swap(unsigned int *ar, unsigned int first, unsigned int second)
{
	unsigned int temp = ar[first];
	ar[first] = ar[second];
	ar[second] = temp;
}

static void reverse(unsigned int *ar, size_t len)
{
	unsigned int i, j;

	for (i = 0, j = len - 1; i < j; i++, j--) {
		swap(ar, i, j);
	}
}

unsigned int next_permutation(unsigned int *ar, size_t len)
{
	unsigned int i1, i2;
	unsigned int result = 0;
	
	/* Find the rightmost element that is the first in a pair in ascending order */
	for (i1 = len - 2, i2 = len - 1; ar[i2] <= ar[i1] && i1 != 0; i1--, i2--);
	if (ar[i2] <= ar[i1]) {
		/* If not found, array is highest permutation */
		reverse(ar, len);
	}
	else {
		/* Find the rightmost element to the right of i1 that is greater than ar[i1] */
		for (i2 = len - 1; i2 > i1 && ar[i2] <= ar[i1]; i2--);
		/* Swap it with the first one */
		swap(ar, i1, i2);
		/* Reverse the remainder */
		reverse(ar + i1 + 1, len - i1 - 1);
		result = 1;
	}
	return result;
}