"Often it appears that there is no better way to solve a problem
than to try all possibe solutions.
This approach, called exhaustive search, is almost always slow,
but sometimes it is better than nothing."
—Ian Parberry, Problems on Algorithms

Algoritmos de enumeração

Para resolver certos problemas é necessário enumerar — ou seja, fazer uma lista de — todos os objetos de um determinado tipo. O número de objetos é tipicamente muito grande, e portanto os algoritmos enumerativos usualmente consomem uma enorme quantidade de tempo.

Os algoritmos enumerativos não são complexos, mas têm suas sutilezas. As versões recursivas são particularmente úteis e interessantes.

Problemas de enumeração estão relacionado com palavras-chave como busca exaustiva, força bruta, backtracking, branch-and-bound.

Enumeração de subseqüências

Vamos adotar e a abreviatura 1..n para 1, 2, ... , n e a abreviatura s[1..k] para s[1], s[2], ... , s[k].  Uma subseqüência de 1..n é qualquer seqüência  s[1..k]  tal que

1   ≤   s[1]   <   s[2]   <   . . .   <   s[k]   ≤   n .

Em outras palavras, uma subseqüência é o que se obtém quando alguns termos da seqüência são apagados. Exemplo:  2,3,5 é uma subseqüência de 1..5. Nosso problema:

Enumerar todas as subseqüências de  1..n,  ou seja,  fazer uma lista em que cada subseqüência apareça uma e uma só vez.

Há uma correspondência biunívoca óbvia entre subseqüências de 1..n e  subconjuntos  do conjunto {1, 2, . . . , n}. Portanto, o número de subseqüências de 1..n é

2ⁿ .

O número de subseqüências aumenta explosivamente com n:  ele dobra toda vez n aumenta de uma unidade.

Subseqüências em ordem lexicográfica

A ordem em que as subseqüências de 1..n são enumeradas não é muito importante, mas certas ordens são mais naturais que outras. Uma das ordens mais naturais é a lexicográfica (esta é a ordem em que palavras aparecem em um dicionário). Uma subseqüência r[1..j] é lexicograficamente menor que s[1..k] se

1.   existe i tal que  r[1..i-1] = s[1..i-1]  e  r[i] < s[i]  ou
2.   j < k  e  r[1..j] = s[1..j] .

Exemplo: Eis a lista, em ordem lexicográfica, de todas as subseqüências não-vazias de 1..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

A lista do exemplo poderia ter sido gerada pela seguinte função.

// Recebe n >= 1 e imprime todas as subseqüências
// não-vazias de 1..n em ordem lexicográfica.

void subseqLex (int n)
{ 
   int *s, k;    
   s = mallocX ((n+1) * sizeof (int));
   s[0] = 0;
   k = 0;

   while (1) {
      if (s[k] < n) {
         s[k+1] = s[k] + 1;
         k += 1;
      } else {
         s[k-1] += 1;
         k -= 1;
      }
      if (k == 0) break;
      imprima (s, k);
   }
}

Cada iteração começa com uma subseqüência s[1..k] de 1..n. A primeira iteração começa com a subseqüência vazia. Cada iteração gera a sucessora de s[1..k] na ordem lexicográfica. Se s[1..k] não tiver sucessora, o processo termina.

Observações:

• A expressão imprima (s, k) não faz mais que imprimir s[1..k].
• A "sentinela" s[0] foi definida para que a instrução s[k-1] += 1 possa ser executada quando k é 1, coisa que acontece somente na última iteração.
• Note que s[1..k] se comporta como uma pilha, com topo s[k]. 

Subseqüências em ordem lexicográfica: versão recursiva

A versão recursiva de subseqLex é muito interessante. A interface com o usuário fica a cargo da seguinte função-"embalagem":

// A função subseqLex2 recebe n e imprime,
// em ordem lexicográfica,
// todas as subseqüências não-vazias de 1..n.

void subseqLex2 (int n)
{
   int *s;    
   s = mallocX ((n+1) * sizeof (int));
   recurs (s, 0, 1, n);
}

O serviço pesado é todo executado pela função recursiva recurs. Para cada valor de m, ela imprima todas as subseqüências que incluem m e depois todas as que não incluem m.

void recurs (int s[], int k, int m, int n)
{
   if (m <= n) {
      s[k+1] = m;
      imprima (s, k+1);
      recurs (s, k+1, m+1, n); // inclui m
      recurs (s, k,   m+1, n); // não inclui m
   }
}

Que coisa faz, exatamente, a função recurs? Como explicar o funcionamento da função? Eis a resposta:

   A função recurs recebe s[1..k] e m e imprime,
   em ordem lexicográfica, cada uma das subseqüências
   não-vazias de m..n precedida do prefixo s[1..k].
   Em outras palavras, imprime todas as seqüências que
   têm a forma s[1..k]t[k+1...], sendo t[k+1...] uma
   subseqüência não-vazia de m..n.

Exemplo: Suponha que s[1] vale 2, que s[2] vale 4 e que n vale 9. Então o comando recurs (s,2,7,n) gera a lista

     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

A primeira linha é gerada por imprima (s,3); as três linhas seguintes são geradas por recurs (s,3,8,n); as demais por recurs (s,2,8,n).

Portanto, recurs (s,0,1,n) faz exatamente o que queremos: imprime todas as subseqüências de 1..n que têm a forma t[1...] com t[1] ≥ 1, ou seja, imprime todas as subseqüências não-vazias de 1..n.

Exercícios

Subseqüências em ordem lexicográfica especial

A ordem lexicográfica "especial" dá preferência às subseqüências mais longas. Eis a definição formal: uma subseqüência r[1..j] precede s[1..k] na ordem lexicográfica especial se

1.  existe i tal que r[1..i-1] é igual a s[1..i-1] e r[i] < s[i]  ou
2.  j > k  e  r[1..k] é igual a s[1..k] .

Exemplo: Eis a lista, em ordem lexicográfica especial, de todas as subseqüências de 1..4:

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

A lista do exemplo poderia ter sido gerado pela seguinte função iterativa:

void subseqLexEsp (int n) { 
   int *s, k;    
   s = mallocX ((n+1) * sizeof (int));
   s[1] = 0;
   k = 1;
   while (1) {
      if (s[k] == n) {
         k -= 1; 
         if (k == 0) break;
      } else {
         s[k] += 1; 
         while (s[k] < n) {
            s[k+1] = s[k] + 1;
            k += 1;
         }
      }
      imprima (s, k);
   }
}

Eis a versão recursiva da função:

// A função subseqLexEsp2 recebe n e imprime todas
// as subseqüências de 1..n (inclusive a subseqüência
// vazia).

void subseqLexEsp2 (int n) {
   int *s;    
   s = mallocX ((n+1) * sizeof (int));
   recursEsp (s, 0, 1, n);
}

// A função auxiliar recursEsp recebe s[1..k] e m
// tais que 1 <= s[1] < ... < s[k] < m e imprime,
// em ordem lexicográfica especial,
// . todas as subseqüências da forma
//   s[1..k]t[k+1..] com t[k+1] >= m
// . e, em seguida, a seqüência s[1..k].

void recursEsp (int s[], int k, int m, int n) {
   if (m > n) imprima (s, k);
   else {
      s[k+1] = m;
      recursEsp (s, k+1, m+1, n); // inclui m
      recursEsp (s, k,   m+1, n); // não inclui m
   }
}

Exemplo: Suponha que s[1] vale 2, que s[2] vale 4 e que n vale 9. Então o comando recursEsp (s,2,7,n) imprime a lista

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

Portanto, recurs (s,0,1,n) imprime todas subseqüências de 1..n, inclusive a vazia.

Exercícios

Mais exercícios