We can solve many problems using combinatorial search, which means using recursion to explore an exponential space.
Let's write a method that prints out all strings of length n containing only characters from the set {'a', 'b', 'c'}. We will denote this set of strings by Sn.
As always, with recursion we need a base case and a recursive case. The base case is easy: if n = 0, then there is only one such string, namely the empty string. In other words, S0 = { ∅ }.
For the recursive case, notice that for n > 0, every string in Sn consists of one of the characters {'a', 'b', 'c' } followed by a string in Sn-1. In other words,
Sn = { c + s | c ∈ { 'a', 'b', 'c' } ∧ s ∈ Sn-1 }
We can explore this set recursively, using a prefix argument that accumulates strings as recursive calls are made. We will print out each string in the base case.
Another way to understand this is that we want to recursively explore a tree of possibilities. At each interior node of the tree, there are three branches corresponding to the three choices we can make ('a', 'b' or 'c'). As we descend the tree, we use the prefix argument to accumulate the characters along the path from the root to the current node. When we reach any leaf node, we print the path.
Here is an implementation:
// Write all n-character strings with characters 'a'..'c', prefixing each with (prefix)
static void abc(string prefix, int n) {
if (n == 0)
WriteLine(prefix);
else
for (char c = 'a' ; c <= 'c' ; ++c)
abc(prefix + c, n - 1);
}
static void abc(int n) => abc("", n);Let's now write a procedure to write all permutations of a string s, which we will denote by Ps. We can do this recursively based on these observations:
In the base case, s is the empty string "".
Then P contains only the empty string, i.e. P = { ""
}.
In the recursive case where length(s) > 0, each permutation consists of some character c ∈ s followed by a permutation of (s – c), which is the string that results from removing c from s. In other words,
Ps = { c + t | c ∈ s ∧ t ∈ Ps – c }
The code below implements this, using a prefix argument to write each accumulated string in the base case.
// Print all permutations of s, prefixed with the given prefix.
static void permute(string prefix, string s) {
if (s == "")
WriteLine(prefix);
else
for (int i = 0 ; i < s.Length ; ++i)
permute(prefix + s[i], s.Remove(i, 1));
}
static void permute(string s) => permute("", s);Now let's write a method that prints all of the 2N subsets of the integers { 1 .. N }.
// Write all subsets of 1 .. N, prefixed with the given prefix.
static void subsets(string prefix, int n) {
if (n == 0)
WriteLine(prefix);
else {
subsets(prefix + n + " ", n – 1); // generate subsets including n
subsets(prefix, n – 1); // generate subsets not including n
}
}
static void subsets(int n) => subsets("", n);Instead of accumulating the output using a prefix string as in the examples above, we can use an array to accumulate the output values. This is more efficient, and allows us to access the accumulated values easily at every step.
Here's an implementation of the problem 'abc x N' that we saw above, using an array rather than a prefix string:
// N-letter sequences, with an array
static void abc1(char[] a, int i, int n) {
if (i == n)
WriteLine(new string(a));
else
for (char c = 'a'; c <= 'c' ; ++c) {
a[i] = c;
abc1(a, i + 1, n);
}
}
static void abc1(int n) => abc1(new char[n], 0, n);A composition of a positive integer N is a sequence of positive integers that add up to N.
Write a method that takes an integer N and prints all its compositions. For example, if N = 4, the output could be
4 3 + 1 2 + 2 2 + 1 + 1 1 + 3 1 + 2 + 1 1 + 1 + 2 1 + 1 + 1 + 1
Solution:
static void compositions(string prefix, int n) {
if (n == 0)
WriteLine(prefix);
else
for (int i = n ; i >= 1 ; --i) {
string s = prefix == "" ? i.ToString() : prefix + " + " + i;
compositions(s, n - i);
}
}
static void compositions(int n) => compositions("", n);
A partition of a positive integer N is a set of positive integers that add up to N.
Write a method that takes an integer N and prints all its partitions. For example, if N = 5, the output could be
5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1
Solution:
static void partitions(string prefix, int n, int max) {
if (n == 0)
WriteLine(prefix);
else
for (int i = Min(n, max) ; i >= 1 ; --i) {
string s = prefix == "" ? i.ToString() : prefix + " + " + i;
partitions(s, n - i, i);
}
}
static void partitions(int n) => partitions("", n, n);Is it possible to place 8 queens on a chessboard so that none of them attack each other? Write a C# program that can search for a solution and print it in this form:
. . Q . . . . . Q . . . . . . . . . . Q . . . . …
Solution:
// Print the board.
static void print(int[] a) {
for (int r = 0 ; r < a.Length ; ++r) {
for (int c = 0 ; c < a.Length ; ++c)
Write(a[c] == r ? "Q " : ". ");
WriteLine();
}
}
// Return true if we can set a[k] = row without attacking any of the k queens
// that have already been placed.
static bool valid(int row, int k, int[] a) {
for (int i = 0 ; i < k ; ++i)
if (a[i] == row || Abs(a[i] - row) == k - i)
return false;
return true;
}
// Find a solution, given that k queens have already been placed.
// a[i] holds the row number of the queen in column i.
static bool queens(int k, int[] a) {
if (k == a.Length) {
print(a); // found a solution
return true;
}
for (int row = 0 ; row < a.Length ; ++row)
if (valid(row, k, a)) {
a[k] = row;
if (queens(k + 1, a))
return true;
}
return false;
}
static void queens(int n) => queens(0, new int[n]);