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 branchandbound.
Table of contents:
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 onetoone 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.


The number of subsequences of 1 . . n grows explosively with n since it doubles every time n increases by 1.
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 s_{1} s_{2} s_{3} . . . s_{k} 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[k1] += 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[k1] += 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 leftrootright traversal of a binary tree.
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[k1] += 1; k; } }
ss[k=1] = 1; print (ss, 1); while (ss[1] < n) { if (ss[k] < n) { ss[k+1] = ss[k] + 1; ++k; } else { ss[k1] += 1; k; } print (ss, k); }
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..m1 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]).
A B C AB AC BC ABC
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.
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
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.


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:


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[n1], 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 = n1; 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; }
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 >= n1) 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; }
ABC ACB BAC BCA CBA CAB
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.)