Permutations

How many ways can three letters be lined up, and how would a program list them all? Choose the first letter, then line up the rest the same way. Watch every ordering of “dsp” appear.

⋯5void swap_chars(char *a, char *b)6{7    char t = *a;8    *a = *b;9    *b = t;10}11 12void permute(char *s, int k, int n)13{14    if (k == n) {15        printf("%s\n", s);16        leaves++;17        return;18    }19    for (int i = k; i < n; i++) {20        swap_chars(&s[k], &s[i]);21        permute(s, k + 1, n);22        swap_chars(&s[k], &s[i]);23    }24}25 26int main(void)27{28    char s[] = "dsp";29    permute(s, 0, 3);30    printf("%d orderings\n", leaves);31    return 0;32}

Fix one, order the rest

To list every ordering of d, s and p: put each letter first in turn, and after each, list every ordering of the two letters left. Two letters have two orderings, so three letters have 3 × 2 = 6. In general n letters have n × (n − 1) × … × 1 = n! orderings, written n factorial.

“List every ordering of the letters left” is the same task on a shorter string, so the function calls itself. The only state it needs is where the fixed part ends.

The code and its cost

The recursion on k

void permute(char *s, int k, int n)
{
    if (k == n) {
        printf("%s\n", s);
        leaves++;
        return;
    }
    for (int i = k; i < n; i++) {
        swap_chars(&s[k], &s[i]);
        permute(s, k + 1, n);
        swap_chars(&s[k], &s[i]);
    }
}

permute(s, k, n) assumes the places before k are fixed. For each i from k to n − 1 it swaps the letter at i into place k, orders the places after k with permute(s, k + 1, n), and swaps back. When k reaches n every place is fixed, and it prints the string. main calls permute(s, 0, 3) on char s[] = "dsp" and the program prints dsp, dps, sdp, spd, psd, pds and 6 orderings.

The swap back

Every call works on main’s one array: s is a pointer to it, not a copy. So when a call returns, the next turn of its caller’s loop must find the letters as they were. The swap back restores them, and after permute returns, s is “dsp” again.

Without it the letters drift. no-swap-back.c drops the second swap and runs on “abc”: it prints abc, acb, cab, cba, abc, acb. Two orderings appear twice, and bac and bca never appear.

Counting

For three letters there is 1 call with k = 0, 3 with k = 1, 6 with k = 2 and 6 with k = 3, the leaves that print: 16 calls. The loops turn 15 times, and each turn makes two swaps, 30 in all, counting a letter swapped with itself.

For n letters the calls are 1 + n + n(n − 1) + … + n! + n!, the last two terms being the calls at k = n − 1 and the leaves. There are n! leaves, and printing them writes about n · n! characters, so the time grows faster than any power of n.

It also grows faster than 2ⁿ, the number of subsets of n items. Going from n − 1 to n multiplies n! by n but 2ⁿ only by 2. So n! is behind at first, 6 against 8 for n = 3, overtakes at n = 4, 24 against 16, and then pulls away: 3,628,800 against 1,024 for n = 10.

Backtracking

The same shape, try a choice, go deeper, undo the choice, solves search problems: place one item, continue, and step back when the rest cannot work. Backtracking adds one thing: it abandons a branch as soon as it is clear that no ordering below it can succeed, instead of building every leaf.

Worked example

Four letters. n = 4 gives 24 orderings and 1 + 4 + 12 + 24 + 24 = 65 calls. permute-count.c counts them on “abcd”, and s is “abcd” again at the end.

One turn, letter by letter. Back in the first call (k = 0) after the d branch, s reads dsp again and i becomes 1. The swap of places 0 and 1 gives sdp, with s fixed first. The call with k = 1 swaps place 1 with itself, and its child prints sdp. It then swaps places 1 and 2, giving spd, which is printed, and swaps them back to sdp. Returning to the first call, the swap back of places 0 and 1 restores dsp, ready for i = 2 to put p first.

Ten letters. 10! = 3,628,800 orderings.

Without the swap back. abc, acb, cab, cba, abc, acb: see above.

Four queens. Place 4 queens on a 4 × 4 board so that no two share a row, a column or a diagonal. Place one queen per row, trying each column; if a column is attacked by a queen already placed, skip it at once, and if no column is left in a row, go back and move the queen above. queens.c finds 2 solutions.

Two checks. How many orderings has “dspx”? (24.) What is s after permute returns? (“dsp”, unchanged.)

Where it’s used

Small search problems. Timetables, puzzles and assignments with a handful of choices are solved by trying every ordering, usually with backtracking to cut branches short.

Testing. A function that should not depend on the order of its inputs can be run on every ordering of a small input.

Anagrams. Listing the anagrams of a word is listing its orderings and keeping the real words.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.