Unit 26: Permutations

We have been using recursions to either compute or find a solution to a problem. In this unit, let's look at another useful application of recursion: to generate all possible permutations or combinations of items.

Let's see a simple example of this: generate all permutations of the characters in a string of length $n$. For simplicity, we assume that there is no repetition in the string.

Recursive Formulation

To formulate a recursive solution, as usual, let's simplify the problem. A simpler version of the problem is to permute a string of length $n-1$.

The trivial case is when we generate the permutation of a string with one character. There is only one possible permutation! Now, by wishful thinking, we assume that we know how to generate all permutations of a string of length $n-1$. Here is what we do to generate all permutations of a string of length $n$.

For each character $i$ in the string, we move $i$ to the first position in the string. We have $n-1$ characters left, which we solve recursively, generating all possible permutations with $i$ as the first character.

For example, consider a string length 3, abc. We start with a as the first character, and generate all the permutations of the string bc. We get two permutations abc and acb. The next character is b. We generate all permutations of the string ac. We get bac and bca. Similarly, we get the permutations cab and cba by considering c as the first character and permutating ba.

The Code

The idea above is implemented as the following:

void permute(char a[], long len, long curr) {
  // permute characters a[curr]..a[len-1] and print out a for each permutation.
  if (curr == len-1) {
    cs1010_println_string(a);
    return;
  }

  permute(a, len, curr + 1);
  for (long i = curr + 1; i < len; i += 1) {
    swap(a, curr, i);
    permute(a, len, curr + 1);
    swap(a, i, curr);
  }
}

Lines 3-6 above corresponds to the base case, where we have reached the end of the string, there is only one character left to permutate. Since there is only one possible permutation, we do not need to do anything except to print out the permutated string.

Line 8 permutes the remaining string, a[curr + 1] to a[len - 1], with character a[curr] intact. Lines 9-13 is a for loop which loops through all characters a[curr + 1] to a[len - 1], and swaps each one to the position of a[curr], and recursively permutes the string a[curr + 1]..a[len - 1]. When we are done, we swap back the original a[curr], this is to ensure that the string remains unchanged after permute is called.

Running Time

How efficient is the function permute? We know that for a string of length $n$, there are $n!$ permutations, so the function permute should be at least $n!$. If it runs in $O(n!)$ steps, then our function above is as efficient as it can get.

Let the number of times permute is called when we pass in a string of length $n$ be $T(n)$. Each invocation of permute(a, n, k) calls permute(a, n, k+1) recursively $n-k$ times. The first call to permute is permute(a, n, 0). We stop when we call permute(a, n, n-1). So $T(1) = 1$.

So, we have:

$$T(n) = nT(n-1) = n(n-1)T(n-2) = n(n-1)(n-2)T(n-3) = .. = n(n-1)(n-2)..T(1) = n!$$

We made $n!$ calls to permute, so the function permute is as efficient as it gets.

Problem Set

Problem Set 26.1

In the code above, we assume that the string contains distinct characters. If there are duplicate characters in the string, duplicate permutations will be generated. For instance, if the input is aaa, the code above would print aaa six times.

We can fix this by making a small change to the function permute above so that it does not generate duplicate permutations. This can be done by adding a condition (Line A). Write a boolean function that we can call in Line A to check if we should continue to permute the rest of the string, and therefore avoid generating duplicate permutations when the input string contains duplicate characters.

void permute(char a[], long len, long curr) {
  // permute characters a[curr]..a[len-1] and print out a for each permutation.
  if (curr == len-1) {
    cs1010_println_string(a);
    return;
  }

  permute(a, len, curr + 1);
  for (long i = curr + 1; i < len; i += 1) {
    if (...) { // Line A
      swap(a, curr, i);
      permute(a, len, curr + 1);
      swap(a, i, curr);
    }
  }
}

Appendix: Complete Code Written in Lecture

#include "cs1010.h"
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

void swap(char a[], long i, long j) {
  char temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

void permute(char str[], long n, long k) {
  if (k == n-1) {
    cs1010_println_string(str);
    return;
  }
  permute(str, n, k+1);
  for (long i = k+1; i < n; i+= 1) {
    swap(str, k, i);
    permute(str, n, k+1);
    swap(str, i, k);
  }
}

int main() {
  char *str = cs1010_read_word();
  permute(str, strlen(str), 0);
  free(str);
}