Enumere as estrelas de nossa galáxia.
—

Quantas vezes a palavra "algoritmo" aparece neste sítio?
—

"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

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 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 subsequências

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

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

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

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

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

2ⁿ .

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

Subsequências em ordem lexicográfica

A ordem em que as subsequê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 sequência r[1..j] é lexicograficamente menor que outra 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 subsequê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 subsequências
// não vazias de 1..n em ordem lexicográfica.

void subseqLex( int n)
{ 
   int *s, k;    
   s = mallocc( (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);
   }
   free( s);
}

Cada iteração começa com uma subsequência s[1..k] de 1..n. A primeira iteração começa com a subsequê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]. 

Subsequê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 subsequências não vazias de 1..n.

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

O serviço pesado é todo executado pela função recursiva recurs. Para cada valor de m, ela imprime todas as subsequê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 subsequências
   não vazias de m..n precedida do prefixo s[1..k].
   Em outras palavras, imprime todas as sequências que
   têm a forma s[1..k]t[k+1...], sendo t[k+1...] uma
   subsequê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 subsequências de 1..n que têm a forma t[1...] com t[1] ≥ 1, ou seja, imprime todas as subsequências não vazias de 1..n.

A versão recursiva da função tem uma importante desvantagem em relação à versão iterativa vista acima:  ela usa uma quantidade exponencial de memória. (Essa memória — proporcional a 2ⁿ — é usada pela pilha de recursão.)  A versão iterativa, ao contrário, só precisa da memória "de trabalho" usada para armazenar o vetor s[0..n].

Exercícios

Subsequências em ordem lexicográfica especial

A ordem lexicográfica "especial" dá preferência às subsequências mais longas. Eis a definição formal: uma sequência r[1..j] precede outra 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 subsequê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:

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

void subseqLexEsp( int n) { 
   int *s, k;    
   s = mallocc( (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);
   }
   free( s);
}

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

// Recebe n e imprime todas as subsequências 
// de 1..n (inclusive a subsequência vazia).

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

// Esta função auxiliar recebe s[1..k] e imprime, 
// em ordem lexicográfica especial,
// todas as subsequências da forma s[1..k]t[k+1..]
// onde t[k+1..] é uma subsequência de m..n.
// Em seguida, imprime a sequê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 subsequências de 1..n, inclusive a vazia.

A versão recursiva da função usa uma quantidade de espaço proporcional a 2ⁿ, enquanto a versão iterativa só precisa de espaço proporcional a n.

Exercícios

Mais exercícios