Algoritmos de enumeração NOVO

Enumere as estrelas de nossa galáxia.
um antigo problema

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

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.

Sumário:

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.

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

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

  1. Mostre que há uma correspondência biunívoca entre as subsequências de 1 . . n e os subconjuntos do conjunto {1, 2, … , n}.
  2. Mostre que o número de subsequências de 1 . . n dobra toda vez que somamos 1 ao valor de n.  Deduza daí que o número de subsequências de 1 . . n é  2n.
  3. Antes de ler a próxima seção, pense em como você resolveria o problema. Tente fazer um esboço do seu algoritmo.

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  s1 s2 s3 . . . sk  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

  1. Escreva uma função booleana que decida se uma sequência s[1 . . k] é lexicograficamente menor que uma sequência t[1 . . l].
  2. Que acontece se a função ssLex for executada com parâmetro n igual a 0?  Verifique, cuidadosamente, a correção do código da função nos casos em que n vale 12.
  3. No código de ssLex, a variável k pode crescer mas nunca é comparada com n.  Isso não é um erro?
  4. Analise a seguinte versão alternativa de ssLex:
    ss[0] = 0; ss[k=1] = 1; 
    while (k >= 1) {
       imprime (ss, k);
       if (ss[k] < n) {
          ss[k+1] = ss[k] + 1; ++k; } 
       else {
          ss[k-1] += 1; --k; } }
    
  5. Analise a seguinte versão alternativa de ssLex:
    ss[k=1] = 1;
    imprime (ss, 1);
    while (ss[1] < n) {
       if (ss[k] < n) {
          ss[k+1] = ss[k] + 1; ++k; } 
       else {
          ss[k-1] += 1; --k; }
       imprime (ss, k); }
    
  6. ★ Escreva uma versão da função ssLex que trate o vetor ss[0..k] explicitamente como uma pilha. Use as funções criapilha, empilha, desempilha, pilhavazia e liberapilha para manipular a pilha. Suponha que existe uma função tamanhodapilha que devolve o número de elementos da pilha e uma função imprimepilha que imprime o conteúdo da pilha a partir do seu segundo elemento.
  7. Modifique a função ssLex para que ela produza todas as subsequências não vazias de 0..n-1.
  8. Subset Sum.  Suponha que você emitiu cheques nos valores v[1], . . . , v[n] ao longo de um mês. No fim do mês, o banco informa que um total t foi debitado de sua conta. Quais dos cheques foram descontados? Por exemplo, se v é  61 62 63 64  e  t = 125  então só há duas possibilidades: ou foram debitados os cheques 1 e 4 ou foram debitados os cheques 2 e 3.  Essa é uma instância do seguinte problema da soma de subconjunto, mais conhecido como subset sum:  Dado um número t e um vetor v[1 . . n] de números (não necessariamente todos positivos), encontrar todas as subsequências s[1 . . k] de 1 . . n tais que  v[s[1]] + . . . + v[s[k]] = t.  Escreva uma função que resolva o problema.
  9. Two Sum.  Escreva um algoritmo rápido para o seguinte problema:  dados um vetor v[1 . . n] de números inteiros e um número inteiro t, decidir se existem dois índices distintos i e j tais que  v[i] + v[j] = t(O problema é superficialmente semelhante ao anterior, mas admite um algoritmo muito eficiente.)  Parte 2: Suponha que os elementos do vetor v[1 . . n] são diferentes entre si e calcule todos os pares i j de índices distintos tais que v[i] + v[j] = t.

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

  1. Importante.  Verifique, cuidadosamente, a correção do código de ssLexR nos casos em que n vale 0, 12.
  2. Cadeias de caracteres.  Escreva uma função que imprima todas as subsequências não vazias de uma cadeia de caracteres ASCII dada.  Por exemplo, as subsequências não vazias de ABC são
    A  B  C  AB  AC  BC  ABC
    
  3. O vetor característico de uma subsequência ss[1..k] de 1..n é o vetor  b[1..n]  de bits que indica quais dos elementos 1..n estão em ss[1..k]  (ou seja, b[i] vale 1 se i está na subsequência e vale 0 em caso contrário).  Para n = 5, por exemplo, o vetor característico de  2 3 5  é  0 1 1 0 1 .  Escreva uma função que calcule o vetor característico de uma subsequência ss[1..k] de 1..n.  Escreva uma função que imprima todas as subsequências de 1..n da seguinte maneira: gera todas as sequências de bits b[1..n] em ordem lexicográfica e, para cada sequência de bits, imprime a correspondente subsequência ss[1..k] de 1..n.  (Sugestão: Imagine que um vetor de bits representa um número em notação binária e gere os vetores de bits em ordem numérica crescente.)  Sua função imprime as subsequências em ordem lexicográfica?
  4. Ordem lexicográfica especial.  A ordem lexicográfica especial dá preferência às subsequências mais longas:  uma sequência s é menor que outra t na ordem lexicográfica especial se  (1) s[i] < t[i] para o menor i tal que s[i] ≠ t[i]  ou  (2) j > k e não existe i tal que s[i] ≠ t[i].  Veja, por exemplo, a enumeração de 1..3 em ordem lexicográfica especial:
    1 2 3
    1 2
    1 3
    1
    2 3
    2
    3
    

    Escreva uma função que enumere as subsequências de 1 . . n em ordem lexicográfica especial. Faça uma versão iterativa e outra recursiva.  Os algoritmos são um pouco mais simples que os da ordem lexicográfica usual.

  5. Ordem militar.  As subsequências de 1 . . n podem ser colocadas em ordem militar, ou ordem shortlex.  A figura ilustra a ordem no caso em que n vale 4.  Analise essa ordem. Escreva funções iterativa e recursiva que gerem todas as subsequências de 1 . . n em ordem militar.
    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
    
  6. Problema da bipartição equilibrada.  Dois irmãos receberam uma herança que consiste em n objetos, cada objeto i tendo valor v[i].  É possível dividir a herança v[1 . . n] em duas partes de mesmo valor?  Essa é uma instância do problema da bipartição equilibrada: Dado um vetor v[1 . . n] de números inteiros (não necessariamente todos positivos), encontrar uma subsequência s[1 . . k] de 1 . . n tal que  v[s[1]] + … + v[s[k]]  =  v[t[1]] + … + v[t[nk]] ,  sendo t[1 . . nk] o complemento de s[1 . . k] em 1 . . n.  Escreva uma função que resolva o problema.
  7. Combinações.  Escreva uma função que imprima todas as subsequências de  1 . . n  que têm exatamente  k  elementos.  (Isso corresponde aos subconjuntos de {1, 2, . . . , n} que têm exatamente k elementos.)

Enumeração de permutações NOVO

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.

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

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:

  • 1 2 3 4
  • 1 2 4 3
  • 1 3 2 4
  • 1 3 4 2
  • 1 4 2 3
  • 1 4 3 2
  • 2 1 3 4
  • 2 1 4 3
  • 2 3 1 4
  • 2 3 4 1
  • 2 4 1 3
  • 2 4 3 1
  • 3 1 2 4
  • 3 1 4 2
  • 3 2 1 4
  • 3 2 4 1
  • 3 4 1 2
  • 3 4 2 1
  • 4 1 2 3
  • 4 1 3 2
  • 4 2 1 3
  • 4 2 3 1
  • 4 3 1 2
  • 4 3 2 1
  •       ⋮
  • 2 5 4 3 1
  • 3 1 2 4 5
  • 3 1 2 5 4
  • 3 1 4 2 5
  • 3 1 4 5 2
  • 3 1 5 2 4
  • 3 1 5 4 2
  • 3 2 1 4 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

  1. Prove que há exatamente  n!  permutações de 1 . . n.
  2. Importante.  Verifique, cuidadosamente, a correção do código da função indiana nos casos em que n vale 1, 2, e 3.
  3. ★ Mostre que função indiana está correta, ou seja, produz a sucessora lexicográfica da permutação que recebeu. (Sugestão: Denote por pp' a permutação que a função produz. Mostre que qualquer permutação que seja lexicograficamente maior que pp é igual a pp' ou é lexicograficamente maior que pp'.)
  4. ★ Escreva uma função que imprima todas as permutações de 1..n invocando indiana repetidamente.
  5. Um algoritmo clássico.  Analise o seguinte algoritmo recursivo clássico de enumeração de permutações de 1..n. O que faz, exatamente, a função recursiva permsComPrefixo? As permutações são impressas em ordem lexicográfica?
    void permutacoes (int n) {
       int* pp;    
       pp = malloc ((n+1) * sizeof (int));
       for (int i = 1; i <= n; i++) pp[i] = i;
       permsComPrefixo (pp, 0, n);
       free (pp);
    }
    static void permsComPrefixo (int* pp, int i, int n) {
       if (i >= n-1)
          imprime (pp, n);
       else {
          for (int j = i+1; j <= n; j++) {
             troca (pp, i+1, j);
             permsComPrefixo (pp, i+1, n);
             troca (pp, i+1, j); } }
    }
    static void troca (int* pp, int k, int j) {
       int t = pp[k]; pp[k] = pp[j]; pp[j] = t; 
    }
    
  6. Permutação de cadeias de caracteres.  Escreva uma função que imprima todas as permutações de uma cadeia de caracteres ASCII dada.  Por exemplo, ao receber a cadeia ABC, a função deve imprimir
    ABC  ACB  BAC  BCA  CBA  CAB 
    

Exercícios 5: aplicações

  1. Problema das rainhas.  É possível colocar 8 rainhas do jogo de xadrez sobre o tabuleiro 8-por-8 de modo que nenhuma delas possa atacar outra?  Escreva uma função que enumere todas as maneiras de dispor n rainhas num tabuleiro n-por-n.  Uma disposição das rainhas pode ser representada por um vetor pp[1 . . n] tal que a rainha da linha i fica na coluna pp[i].
  2. Passeio do cavalo.  Suponha dado um tabuleiro de xadrez n-por-n. Determine se é possível que um cavalo do jogo de xadrez parta da posição (1,1) do tabuleiro e passe exatamente uma vez por cada uma das demais posições do tabuleiro. Por exemplo, para um tabuleiro 5-por-5 uma solução do problema é
     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
    

    (Sugestão: Numere as casas do tabuleiro da maneira óbvia: a primeira linha da esquerda para a direita, depois a segunda linha, etc.  Agora examine todas as permutações de 1 2 . . . n2.  Para cada permutação, verifique se ela representa um passeio válido.)

  3. Permutação cíclica.  Uma permutação cíclica de uma sequência s1 s2 . . . sn é qualquer sequência da forma  sk sk+1 . . . sn s1 s2 . . . sk−1.  Escreva uma função que decida se uma sequência t1 t2 . . . tn é permutação cíclica de s1 s2 . . . sn.
  4. Permutação aleatória.  Escreva uma função que produza uma permutação aleatória de 1 . . n. A função deve produzir, com igual probabilidade, qualquer uma das n! permutações de 1 . . n.
  5. Distância tau de Kendall.  Como medir a distância entre duas permutações?  Veja exercício no capítulo do algoritmo Mergesort.
  6. Desarranjos.  Um desarranjo (= derangement) da sequência 1 . . n é qualquer permutação dessa sequência que muda todos os termos de posição. Em outras palavras, um desarranjo de 1 . . n é qualquer permutação p[1 . . n]  de 1 . . n tal que p[i] ≠ i para todo i.  Por exemplo, os 9 desarranjos de 1 2 3 4 são  2 1 4 32 3 4 12 4 1 33 1 4 23 4 1 23 4 2 14 1 2 34 3 1 24 3 2 1.  Escreva uma função que imprima cada desarranjo de 1 . . n exatamente uma vez.
  7. Partições.  Escreva uma função que imprima uma lista de todas as partições do conjunto {1, 2, . . . , n} em m blocos não vazios. Você pode representar uma tal partição por um vetor w[1 . . n] com valores em 1 . . m dotado da seguinte propriedade: para cada i em 1 . . m existe j tal que w[ j] = i.