Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Algoritmos de enumeração

Para resolver certos problemas computacionais é necessário enumerar — ou seja, fazer uma lista de — todos os objetos de um determinado tipo (por exemplo, todas as sequências crescentes de números inteiros entre 1 e 999, ou todas as árvores binárias de busca com chaves entre 1 e 999).  O número de objetos é tipicamente muito grande, e portanto sua enumeração consome muito tempo.

Os algoritmos de enumeração não são complexos, mas têm suas sutilezas. As versões recursivas são particularmente úteis e interessantes.  Algoritmos de enumeração têm relação com conceitos como backtracking, busca exaustiva, força bruta, e branch-and-bound.

Enumeração de sequências

Os objetos principais deste capítulo são sequências de números inteiros, como  9 51 61 4 8 3 18 51 13 22 1 3  por exemplo.  Usaremos ⚠ a abreviatura especial  1 . . n  para a sequência  1 2 3 . . . n .  De modo mais geral, usaremos a abreviatura m . . n  para a sequência  m m+1 m+2 . . .  n .  Se m > n, a sequência é vazia.

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

É claro que uma subsequência de 1 . . n é o mesmo que uma sequência estritamente crescente de alguns elementos do conjunto {1, 2, … , n}.  É claro também que há uma correspondência biunívoca entre as subsequências de 1 . . n e os subconjuntos de {1, 2, … , n}.

A ordem em que as subsequências de 1 . . n são enumeradas não é muito importante. Veja, por exemplo, as seguintes enumerações das subsequências não vazias de 1 . . 4:  a primeira está em ordem militar, enquanto a segunda está em ordem lexicográfica.

O número de subsequências de 1 . . n cresce explosivamente com n pois dobra toda vez que n aumenta em 1.

Exercícios 1

Subsequências em ordem lexicográfica

Nossa solução do problema vai listar as subsequências de 1 . . n em ordem lexicográfica.  Dada uma subsequência ss, nosso algoritmo gerará sua sucessora lexicográfica, ou seja, a menor subsequência que é maior que ss, sendo menor e maior tomados no sentido lexicográfico.  Por exemplo, no conjunto de todas as subsequências de 1 . . 9 , a sucessora lexicográfica de  2 4 5 7 8  é  2 4 5 7 8 9  e a sucessora lexicográfica de  2 4 5 7 9  é  2 4 5 8.

Sequências serão representadas por vetores. Assim, uma sequência como  s₁ s₂ s₃ . . . s_k  será denotada simplesmente por  s[1..k].  Por conveniência, as sequências e vetores serão indexados a partir de 1 e não a partir de 0, como é mais comum em C.

Para transformar uma subsequência ss[1..k] de 1..n na sua sucessora lexicográfica, basta fazer o seguinte:

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

(A operação dentro do bloco else {} é conhecida como backtrack ou volta de ré.)  O código só não está correto em dois casos: (1) se o valor original de k é 0 e (2) se k vale 1 e o valor original de ss[1] é n. No primeiro caso, a sucessora lexicográfica é definida por ss[k=1] = 1. No segundo, não existe sucessora.

Essa discussão leva à seguinte solução do problema de enumeração:

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

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;
      imprime (ss, k);
   }
   free (ss);
}

Cada iteração começa com uma subsequência ss[1..k] de 1..n.  A primeira iteração começa com a subsequência vazia. Cada iteração gera a sucessora lexicográfica de ss[1..k]. Se ss[1..k] não tiver sucessora, o processo termina.  A instrução imprime (ss, k) não faz mais que imprimir ss[1..k].

A sentinela ss[0] cuida da primeira iteração (que começa com k igual a 0) e da última iteração (que começa com ss[k] igual a n e k igual a 1).

O vetor ss[1..k] comporta-se como uma pilha, com topo ss[k].  É curioso como o código de ssLex se assemelha à versão iterativa da varredura e-r-d de uma árvore binária.

Exercícios 2

Subsequências: versão recursiva

A versão recursiva de ssLex é muito interessante. A interface com o usuário fica a cargo da seguinte função-embalagem (= wrapper-function):

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

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

O serviço pesado é todo executado pela função recursiva ssLexComPrefixo, cujo terceiro parâmetro é um índice m entre 1 e n+1:

static void 
ssLexComPrefixo (int ss[], int k, int m, int n)
{
   if (m <= n) {
      // caso 1: inclui m
      ss[k+1] = m;
      imprime (ss, k+1);
      ssLexComPrefixo (ss, k+1, m+1, n);
      // caso 2: não inclui m
      ssLexComPrefixo (ss, k,   m+1, n);
   }
}

(É tentador começar o código da função com  if (m > n) imprime (ss,k);  mas isso não produziria ordem lexicográfica. Veja a ordem lexicográfica especial abaixo.)  O que faz, exatamente, a função ssLexComPrefixo? Como explicar o funcionamento de ssLexComPrefixo?  Eis a resposta:

// A função ssLexComPrefixo recebe m <= n+1
// e uma subsequência ss[1..k] de 1..m-1
// e imprime, em ordem lexicográfica,
// todas as subsequências não vazias de m..n
// cada uma precedida do prefixo ss[1..k].

Em outras palavras, imprime todas as sequências da forma x[1..k..l] tais que x[1..k] = ss[1..k] e x[k+1..l] é uma subsequência não vazia de m..n.

Suponha, por exemplo, que ss[1] = 2, ss[2] = 4, e n = 9. Então a chamada ssLexComPrefixo (ss, 2, 7, n) imprime 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 é produzida por imprime (ss,3);  as três linhas seguintes são produzidas por ssLexComPrefixo (ss, 3, 8, n);  e as demais, por ssLexComPrefixo (ss, 2, 8, n).

Portanto, a chamada ssLexComPrefixo (ss, 0, 1, n) no código de ssLexR faz exatamente o que queremos: imprime todas as subsequências não vazias de 1..n (com prefixo vazio).

A função ssLexR tem uma séria desvantagem em relação à sua versão iterativa:  a pilha de execução da versão recursiva consome bem mais espaço na memória que a versão iterativa (que só precisa de espaço para armazenar ss[0..n+1]).

Exercícios 3

Enumeração de permutações

Uma permutação da sequência  1 . . n  é qualquer rearranjo dos termos dessa sequência.  Em outras palavras, uma permutação de 1 . . n é qualquer sequência p[1 . . n] em que cada elemento de 1 . . n aparece uma e uma só vez.  É fácil verificar que há exatamente n! permutações de 1 . . n.

Nosso problema: Enumerar as permutações de 1 . . n,  ou seja,  produzir uma lista em que cada permutação de 1 . . n apareça uma e uma só vez.

Na prática, a enumeração das permutações de 1 . . n só é razoável para valores muito modestos de n, uma vez que o número de permutações cresce explosivamente à medida que n aumenta.

A ordem em que as permutações são enumeradas não é muito importante. Na seguinte figura temos duas enumerações das permutações de 1 2 3 4: a primeira está em ordem recursiva clássica, enquanto a segunda está em ordem lexicográfica.

Na lista de permutações em ordem lexicográfica, a primeira permutação é crescente e a última é decrescente. Esse padrão se repete recursivamente da seguinte maneira: todas as permutações que têm um determinado prefixo, digamos pp[1..i], aparecem consecutivamente na lista e o correspondente sufixo, pp[i+1..n], é crescente na primeira permutação e decrescente na última.  Veja um exemplo com n = 4 e outro com n = 5:

Esse padrão é a base de um antigo algoritmo indiano para o problema.  O coração do algoritmo é uma função que recebe uma permutação qualquer pp[1..n] e constrói sua sucessora lexicográfica, ou seja, a menor permutação que é maior que pp[1..n], sendo menor e maior tomados no sentido lexicográfico.  Por exemplo, a partir da permutação  2 5 4 3 1  constrói a permutação  3 1 2 4 5.

A função constrói a sucessora lexicográfica em quatro passos: (1) encontra o menor i tal que pp[i+1..n] é decrescente, (2) encontra o único k em i+1..n tal que pp[k] > pp[i] > pp[k+1], (3) troca os valores de pp[i] e pp[k], (4) inverte pp[i+1..n], trocando pp[i+1] com pp[n], depois pp[i+2] com pp[n-1], etc.

// Recebe uma permutação pp[1..n] de 1..n. Se
// pp[1..n] não tem sucessora lexicográfica, 
// devolve 0. Senão, devolve 1 e armazena em
// pp[1..n] a sucessora lexicográfica da 
// permutação dada.

int
indiana (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] e
   // pp[i+1..n] é decrescente
   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] é decrescente
   i += 1;
   k = n;
   while (i < k) {
      t = pp[i]; pp[i] = pp[k]; pp[k] = t;
      i++; 
      k--;
   }
   // pp[i+1..n] é crescente
   return 1;
}

Exercícios 4

Exercícios 5: aplicações