Algorithms Design   |   C language   |   Index

Enumeration 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.

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

Exercises 1

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  s₁ s₂ s₃ . . . 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[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

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

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.

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[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

Exercises 5: applications