Enumeration algorithms

Often it appears that
there is no better way to solve a problem
than to try all possible solutions.
This approach, called exhaustive search,
is almost always slow,
but sometimes it is better than nothing.

Ian Parberry, Problems on Algorithms

To solve certain computational problems, we must enumerate — that is, make a list of — all the objects of a certain kind (for example, all the increasing sequences of integers between 1 and 999, or all the binary search trees with keys between 1 and 999).  The number of objects is typically very large, and therefore the enumeration is time consuming.

The enumeration algorithms are not complex, but they have their subtleties. The recursive versions are particularly useful and interesting.  Enumeration algorithms are related to concepts like backtracking, exhaustive search, brute force, and branch-and-bound.

Enumeration of sequences

The main objects of this chapter are sequences of integers, like  9 51 61 4 8 3 18 51 13 22 1 3  for example.  We shall use ⚠ the shorthand  1 . . n  for the sequence  1 2 3 . . . n.  More generally, m . . n  will be our shorthand for the sequence  m m+1 m+2 . . .  n.  If m > n, this sequence is empty.

Our problem: Enumerate the subsequences of  1 . . n,  i.e.,  make a list in which each subsequence of  1 . . n appears exactly once.

A subsequence of 1 . . n is, of course, the same thing as a strictly increasing sequence of some elements of the set {1, 2, … , n}.  Moreover, there is a one-to-one correspondence between the subsequences of 1 . . n and the subsets of {1, 2, … , n}.

The order in which the subsequences of 1 . . n are enumerated is not very important. See, for example, the following enumerations of the nonempty subsequences of 1 . . 4:  the first is in military order, while the second is in lexicographic order.

 1 2 3 4 1 2 1 3 1 4 2 3 2 4 3 4 1 2 3 1 2 4 1 3 4 2 3 4 1 2 3 4 1 1 2 1 2 3 1 2 3 4 1 2 4 1 3 1 3 4 1 4 2 2 3 2 3 4 2 4 3 3 4 4

The number of subsequences of 1 . . n grows explosively with n since it doubles every time n increases by 1.

Exercises 1

1. Show that there is a one-to-one correspondence between the subsequences of 1 . . n and the subsets of the set {1, 2, … , n}.
2. Show that the number of subsequences of 1 . . n doubles every time we add 1 to the value of n.  Deduce that the number of subsequences of 1 . . n is  2n.
3. Before reading the next section, think about how you would solve the problem. Try to sketch your algorithm.

Subsequences in lexicographic order

Our solution of the problem will list the subsequences of 1 . . n in lexicographic order.  Given a subsequence ss, our algorithm will generate its lexicographic successor, that is, the smallest subsequence greater than ss, where smaller and greater are taken in lexicographic sense.  For example, in the set of all the subsequences of 1 . . 9 , the lexicographic successor of  2 4 5 7 8  is  2 4 5 7 8 9  and the lexicographic successor of  2 4 5 7 9  is  2 4 5 8.

Sequences will be represented by arrays. Hence, a sequence like  s1 s2 s3 . . . sk  will be denoted simply by  s[1..k].  It is convenient to start the indexing from 1 rather than from 0 (as is usual in C).

To transform a subsequence ss[1..k] of 1..n into its lexicographic successor, we can do the following:

```if (ss[k] < n) {
ss[k+1] = ss[k] + 1;
++k;
} else {
ss[k-1] += 1;
--k;
}
```

(The operation within the else {} block is known as backtracking.)  The code is correct except for two cases: (1) when the original value of k is 0 and (2) when k is 1 and the original value of ss[1] is n. In the first case, the lexicographic successor is defined by ss[k=1] = 1. In the second case, there is no successor.

This discution leads to the following solution of the enumeration problem:

```// Receives n >= 1 and prints all the
// nonempty subsequences of 1..n,
// in lexicographic order.

void
ssLex (int n)
{
int* ss, k;
ss = malloc ((n+1) * sizeof (int));
ss[k=0] = 0;

while (true) {
if (ss[k] < n) {
ss[k+1] = ss[k] + 1;
++k;
} else {
ss[k-1] += 1;
--k;
}
if (k == 0) break;
print (ss, k);
}
free (ss);
}
```

Each iteration begins with a subsequence ss[1..k] of 1..n.  The first iteration begins with the empty subsequence. Each iteration generates the lexicographic successor of ss[1..k]. If ss[1..k] has no successor, the process terminates.  The instrution print (ss, k) simply prints ss[1..k].

The sentinel ss[0] takes care of the first iteration (that begins with k equal to 0) and of the last iteration (that begins with ss[k] equal to n and k equal to 1).

The array ss[1..k] behaves like a stack, with top ss[k].  Interestingly, the code of ssLex resembles that of the iterative version of the left-root-right traversal of a binary tree.

Exercises 2

1. Write a booleana function that will decide whether a sequence s[1 . . k] is lexicographically smaller than a sequence t[1 . . l].
2. What happens if the function ssLex is executed with parameter n equal to 0?  Carefully check the correctness of the code when n is 1 and when n is 2.
3. In the code of ssLex, the variable k may increase but is never compared to n.  Is this an error?
4. Analyse the following alternative version of ssLex:
```ss[0] = 0; ss[k=1] = 1;
while (k >= 1) {
print (ss, k);
if (ss[k] < n) {
ss[k+1] = ss[k] + 1; ++k; }
else {
ss[k-1] += 1; --k; } }
```
5. Analyse the following alternative version of ssLex:
```ss[k=1] = 1;
print (ss, 1);
while (ss[1] < n) {
if (ss[k] < n) {
ss[k+1] = ss[k] + 1; ++k; }
else {
ss[k-1] += 1; --k; }
print (ss, k); }
```
6. ★ Write a version of the function ssLex that treats the array ss[0..k] explicitly as a stack. Use the functions createstack, push, pop, stackisempty and freestack to manipulate the stack. Assume that you have a function sizeofstack that returns the number of elements on the stack and a function printstack that prints the contents of the stack starting from its second element.
7. Modify the function ssLex so that it produces all the nonempty subsequences of 0..n-1.
8. Subset Sum.  Suppose that you wrote n bank checks with values v[1], . . . , v[n] during a given month. At the end of the month, the bank takes a total of t from your account. Which of the checks were cashed? For example, if v is  61 62 63 64  and  t = 125, there are only two possibilidades: either checks 1 and 4 were cashed or checks 2 and 3 were cashed.  This is an instance of the following subset sum problem:  Given a number t and an array v[1 . . n] of numbers (not necessarily all positive), find all the subsequences s[1 . . k] of 1 . . n such that  v[s[1]] + . . . + v[s[k]] = t.  Write an algorithm to solve the problem.
9. Two Sum.  Write a fast algorithm for the following problem:  given an array v[1 . . n] of integers and an integer t, decide whether there are two distinct indices i and j such that  v[i] + v[j] = t(Unlike the previous problem, this one has a very efficient algorithm.)  Part 2: Suppose that the elements of the array v[1 . . n] are pairwise distinct and calcule all the pairs i j of distinct indices for which v[i] + v[j] = t.

Subsequences: recursive version

The recursive version of ssLex is very interesting. The following wrapper function provides the interface between the recursive function and the user:

```// Receives n >= 1 and prints all the
// nonempty subsequences of 1..n,
// in lexicographic order.

void
ssLexR (int n)
{
int* ss;
ss = malloc ((n+1) * sizeof (int));
ssLexPrefix (ss, 0, 1, n);
free (ss);
}
```

The job proper is done by the recursive function ssLexPrefix, whose third parameter is an index m between 1 and n+1:

```static void
ssLexPrefix (int ss[], int k, int m, int n)
{
if (m <= n) {
// case 1: include m
ss[k+1] = m;
print (ss, k+1);
ssLexPrefix (ss, k+1, m+1, n);
// case 2: do not include m
ssLexPrefix (ss, k,   m+1, n);
}
}
```

(It is tempting to begin the code of the function with  if (m > n) print (ss,k);  but this would not produce lexicographic order. See the special lexicographic order below.)  How to explain ssLexPrefix? In other words, what does the function ssLexPrefix do? Here is the answer:

```// The function ssLexPrefix receives m <= n+1
// and a subsequence ss[1..k] of 1..m-1 and
// prints, in lexicographic order, all the
// nonempty subsequences of m..n, each
// preceded by the prefix ss[1..k].
```

In other words, the function prints all the sequences of the form x[1..k..l] such that x[1..k] = ss[1..k] and x[k+1..l] is a nonempty subsequence of m..n.

Suppose, for example, that ss[1] = 2, ss[2] = 4, and n = 9. Then the call ssLexPrefix (ss, 2, 7, n) will print the list

```2 4 7
2 4 7 8
2 4 7 8 9
2 4 7 9
2 4 8
2 4 8 9
2 4 9
```

The first line is produced by print (ss,3); the next three lines are produced by ssLexPrefix (ss, 3, 8, n); the remaining lines, by ssLexPrefix (ss, 2, 8, n).

Hence, the call ssLexPrefix (ss, 0, 1, n) in the code of ssLexR will do exactly what we want: print all the nonempty subsequences of 1..n (with empty prefix).

The function ssLexR has a disadvantage over its iterative version:  the execution stack of the recursive version consumes far more space in memory than the iterative version (which only needs space to store the array ss[0..n+1]).

Exercises 3

1. Important.  Carefully check the correctness of the code of ssLexR and ssLexPrefix in the instances where n is 0, 1, and 2.
2. Subsequences of character chains.  Write a function to print all the nonempty subsequences of a given sequence of ASCII characters.  For example, the nonempty subsequences of ABC are
```A  B  C  AB  AC  BC  ABC
```
3. The characteristic array of a subsequence ss[1..k] of 1..n  is the array  b[1..n]  of bits that indicates which of the elements of 1..n are in ss[1..k]  (that is, b[i] is 1 if i is in the subsequence and is 0 otherwise).  When n = 5, for example, the characteristic array of  2 3 5  is  0 1 1 0 1 .  Write a function to compute the characteristic array of a subsequence ss[1..k] of 1..n.  Write a function to print all the subsequences of 1..n as follows: generate all the bit arrays b[1..n] in lexicographic order and, for each b[1..n], print the corresponding subsequence ss[1..k] of 1..n.  (Hint: Imagine that an array of bits represents a number in binary notation and generate the arrays of bits in increasing numerical order.)  Does your function print the subsequences in lexicographic order?
4. Special lexicographic order.  The special lexicographic order favors the longer subsequences:  a sequence s is smaller that another t in the special lexicographic order if  (1) s[i] < t[i] for the smallest i such that s[i] ≠ t[i]  or  (2) j > k and there is no i such that s[i] ≠ t[i].  For example, see the enumeration of 1..3 in special lexicographic order:
```1 2 3
1 2
1 3
1
2 3
2
3
```

Write a function to enumere the subsequences of 1 . . n in special lexicographic order. Write an iterative version and a recursive version.  The algorithms are a little simpler than those for the usual lexicographic order.

5. Military order.  The subsequences of 1 . . n can be put in military order, or shortlex order.  The figure illustrates the order in case n = 4.  Analyse this order. Write iterative and recursive functions to generate all the subsequences of 1 . . n in military order.
```1
2
3
4
1 2
1 3
1 4
2 3
2 4
3 4
1 2 3
1 2 4
1 3 4
2 3 4
1 2 3 4
```
6. Balanced bipartition.  Two brothers received an inheritance consisting of n objects, each object i having value v[i].  Is it possible to divide the inheritance v[1 . . n] into two parts of equal value?  This is an instance of the following balanced bipartition problem: Given an array v[1 . . n] of (not necessarily positive) integers, find a subsequence s[1 . . k] of 1 . . n such that  v[s[1]] + … + v[s[k]] is equal to v[t[1]] + … + v[t[nk]],  where t[1 . . nk] is the complement of s[1 . . k] in 1 . . n.  Write a function to solve the problem.
7. Combinations.  Write a function to print all the subsequences of  1 . . n  that have exactly  k  elements.  (These subsequences correspond to the k-element subsets of {1, 2, . . . , n}.)

Enumeration of permutations

A permutation of the sequence  1 . . n  is any rearrangement of the terms of the sequence.  In other words, a permutation of 1 . . n is any sequence p[1 . . n] in which each element of 1 . . n appears exactly once.  It is easy to check that there are exactly n! permutations of  1 . . n.

Our problem: Enumerate the permutations of 1 . . n,  i.e.,  produce a list in which each permutation of 1 . . n appears exactly once.

In practice, enumerating the permutations of 1 . . n is reasonable only for very modest values of n, since the number of permutations grows explosively as n increases.

The order in which the permutations are enumerated is not too important. The following figure shows two enumerations of the permutations of 1 2 3 4: the first is in classical recursive order, while the second is in lexicographic order.

 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 3 2 1 4 2 3 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 3 1 2 4 1 3 3 2 1 4 3 2 4 1 3 1 2 4 3 1 4 2 3 4 1 2 3 4 2 1 4 2 3 1 4 2 1 3 4 3 2 1 4 3 1 2 4 1 3 2 4 1 2 3 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1

In the lexicographically ordered list, the first permutation is increasing and the last one is decreasing. This pattern is recursively repeated: all the permutations that have a given prefix, say pp[1..i], appear consecutively in the list and the corresponding suffix, pp[i+1..n], is increasing in the first permutation and decreasing in the last.  See an example with n = 4 and another with n = 5:

 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 ⋮ 2 5 4 3 1 3 1 2 4 5 3 1 2 5 4 3 1 4 2 5 3 1 4 5 2 3 1 5 2 4 3 1 5 4 2 3 2 1 4 5       ⋮

This pattern is the basis of an old Indian algorithm for the problem.  The heart of the algorithm is a function that receives a permutation pp[1..n] and constructs its lexicographic successor (i.e., the smallest permutation that is greater than pp[1..n], where small and great are taken in lexicographic sense).  For example, starting with the permutation  2 5 4 3 1  the algorithm constructs the permutation  3 1 2 4 5.

The construction of the lexicographic successor is carried out in four steps: (1) find the smallest i such that pp[i+1..n] is decreasing, (2) find the only k in i+1..n such that pp[k] > pp[i] > pp[k+1], (3) interchange the values of pp[i] and pp[k], (4) invert pp[i+1..n] by interchanging pp[i+1] with pp[n], then pp[i+2] with pp[n-1], etc.

```// Receives a permutation pp[1..n] of 1..n. If
// pp[1..n] has no lexicographic successor,
// returns 0. Otherwise, returns 1 and stores
// in pp[1..n] the lexicographic successor of
// the original permutation.

int
indian (int* pp, int n)
{
int i, k, t;
i = n-1;
while (i >= 1 && pp[i] > pp[i+1]) i--;
if (i < 1) return 0;
// pp[i] < pp[i+1] and
// pp[i+1..n] is decreasing
k = n;
while (pp[i] > pp[k]) k--;
// pp[k] > pp[i] > pp[k+1]
t = pp[k]; pp[k] = pp[i]; pp[i] = t;
// pp[i+1..n] is decreasing
i += 1;
k = n;
while (i < k) {
t = pp[i]; pp[i] = pp[k]; pp[k] = t;
i++;
k--;
}
// pp[i+1..n] is increasing
return 1;
}
```

Exercises 4

1. Prove that there are exactly  n!  permutations of 1 . . n.
2. Important.  Carefully check the correctness of code of the function indian in the cases where n is 1, 2, and 3.
3. ★ Show that the indian function is correct. In other words, show that the function produces the lexicographic successor of the received permutation.  (Hint: Denote by pp' the permutation that the function produces. Show that any permutation that is lexicographically greater than pp is either equal to pp' or lexicografically greater than pp'.)
4. ★ Write a function to print all the permutations of 1..n by calling function indian repeatedly.
5. A classic algorithm.  Analyse the following classic recursive algorithm for enumerating permutations of 1..n. What exactly does the recursive function permsWithPrefix do? Are the permutations printed in lexicographic order?
```void permutations (int n) {
int* pp;
pp = malloc ((n+1) * sizeof (int));
for (int i = 1; i <= n; i++) pp[i] = i;
permsWithPrefix (pp, 0, n);
free (pp);
}
static void permsWithPrefix (int* pp, int i, int n) {
if (i >= n-1)
print (pp, n);
else {
for (int j = i+1; j <= n; j++) {
swap (pp, i+1, j);
permsWithPrefix (pp, i+1, n);
swap (pp, i+1, j); } }
}
static void swap (int* pp, int k, int j) {
int t = pp[k]; pp[k] = pp[j]; pp[j] = t;
}
```
6. Permutations of character chains.  Write a function that will print all the permutations of a given sequence of ASCII characters.  For example, upon receiving the sequence ABC, the function must print
```ABC  ACB  BAC  BCA  CBA  CAB
```

Exercises 5: applications

1. The eight queens problem.  Is it possible to place 8 queens on a chessboard so that no queen can attack any other?  Write a function to enumere all the ways of placing n queens on an n-by-n chessboard.  A placement of queens can be represented by an array pp[1 . . n] such that the queen on row i is on column pp[i].
2. Knight's tour.  Consider an n-by-n chessboard. Determine whether it is possible for a knight to start in square (1,1) and make a tour visiting each square exactly once. For example, here is a solution for the 5-by-5 board:
``` 1  6 15 10 21
14  9 20  5 16
19  2  7 22 11
8 13 24 17  4
25 18  3 12 23
```

(Hint: Number the squares of the chessboard in the obvious way: the first row from left to right, then the second row, and so on.  Now examine all the permutations of 1 2 . . . n².  For each permutation, check whether it represents a valid tour.)

3. Cyclic permutations.  A cyclic permutation of a sequence s1 s2 . . . sn is any sequence of the form  sk sk+1 . . . sn s1 s2 . . . sk−1.  Write a function to decide whether a sequence t1 t2 . . . tn is a cyclic permutation of s1 s2 . . . sn.
4. Random permutation.  Write a function to produce a random permutation of 1 . . n. The function must produce, with equal probability, any one of the n! permutations of 1 . . n.
5. Kendall tau distance.  How to measure the distance between two permutations?  See exercise in the Mergesort algorithm chapter.
6. Derangements.  A derangement of the sequence 1 . . n is any permutation of this sequence that changes the position of every term. In other words, a derangement is any permutation p[1 . . n]  such that p[i] ≠ i for all i.  For example, the 9 derangements of 1 2 3 4 are  2 1 4 32 3 4 12 4 1 33 1 4 23 4 1 23 4 2 14 1 2 34 3 1 24 3 2 1.  Write a function to print each derangement of 1 . . n exactly once.
7. Partitions.  Write a function to print a list of all the partitions of the set {1, 2, . . . , n} into m nonempty blocks. You can represent such a partition by an array w[1 . . n] with values in 1 . . m having the following property: for each i in 1 . . m there exists j such that w[ j] = i.