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 á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 estão relacionados com ideias como backtracking, busca exaustiva, força bruta, e branch-and-bound.
Sumário:
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. Essas 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.
Usaremos ⚠ a abreviatura especial 1 . . n para a sequência 1 2 3 . . . n . De modo mais geral, m . . n será nossa abreviatura para m m+1 m+2 . . . n . Se m > n, a sequência é vazia.
Sequências são comparadas lexicograficamente. Uma sequência r[1 . . j] é lexicograficamente menor que outra s[1 . . k] se
Nas mesmas condições, dizemos que s[1 . . k] é lexicograficamente maior que r[1 . . j]. Por exemplo, 4 1 3 2 é lexicograficamente maior que 4 1 2 5 6 9 e lexicograficamente menor que 4 1 3 2 5 6 .
Conjuntos finitos de sequências são, muitas vezes, examinados em ordem lexicográfica, da menor para a maior. Uma sequência r do conjunto é a predecessora immediata de outra, digamos s, se for a maior das sequências menores que s na ordem lexicográfica. A sucessora imediata de uma sequência é definida de maneira análoga.
Uma subsequência é o que sobra quando alguns termos de uma sequência são apagados. Mais exatamente, uma subsequência de a[1 . . n] é qualquer sequência s[1 . . k] tal que s[1] = a[i1], s[2] = a[i2], . . . , s[k] = a[ik] para alguma sequência 1 ≤ i1 < i2 < . . . < ik ≤ n de índices. Em particular, subs[1 . . k] é uma subsequência de 1 . . n se
1 ≤ subs[1] < subs[2] < . . . < subs[k] ≤ n .
Por exemplo, 2 3 5 8 é uma subsequência de 1 . . 8.
Nosso problema: Enumerar as subsequências de 1 . . n , ou seja, fazer uma lista em que cada subsequência apareça uma e uma só vez.
O tamanho da lista cresce explosivamente com n pois o número de subsequências de 1 . . n dobra toda vez que n aumenta em 1.
A ordem em que as subsequências de 1 . . n são enumeradas não é muito importante, mas é natural usar a ordem lexicográfica. Veja, por exemplo, a enumeração das subsequências não vazias de 1..4 em ordem lexicográfica:
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
Para transformar uma subsequência subs[1..k] de 1..n na sua sucessora imediata, basta fazer o seguinte:
if (subs[k] < n) {
subs[k+1] = subs[k] + 1;
++k;
} else {
subs[k-1] += 1;
--k;
}
A operação dentro do bloco else {}
é conhecida como backtrack ou volta de ré
.
Esse código só não está correto em dois casos: (1) se o valor original de k é 0 e (2) se o valor original de subs[k] é n e k vale 1. No primeiro caso, a sucessora imediata é definida por subs[k=1] = 1. No segundo, não existe sucessora alguma.
A discussão na seção anterior leva a um algoritmo iterativo que enumera as subsequências não vazias de 1..n:
// Recebe n >= 1 e imprime todas as
// subsequências não vazias de 1..n,
// em ordem lexicográfica.
void
ssLex (int n)
{
int *subs, k;
subs = malloc ((n+1) * sizeof (int));
subs[k=0] = 0;
while (true) {
if (subs[k] < n) {
subs[k+1] = subs[k] + 1;
++k;
} else {
subs[k-1] += 1;
--k;
}
if (k == 0) break;
imprime (subs, k);
}
free (subs);
}
Cada iteração começa com uma subsequência subs[1..k] de 1..n. A primeira iteração começa com a subsequência vazia. Cada iteração gera a sucessora imediata de subs[1..k]. Se subs[1..k] não tiver sucessora, o processo termina. A instrução imprime (subs, k) não faz mais que imprimir subs[1..k].
A sentinela
subs[0]
cuida da primeira iteração
(que começa com k igual a 0)
e da última iteração
(que começa com
subs[k] igual a n e
k igual a 1).
O vetor subs[1..k] comporta-se como uma pilha, com topo subs[k]. É curioso como o código de ssLex se assemelha à versão iterativa da varredura e-r-d de uma árvore binária.
subs[0] = 0; subs[k=1] = 1;
while (k >= 1) {
imprime (subs, k);
if (subs[k] < n) {
subs[k+1] = subs[k] + 1; ++k; }
else {
subs[k-1] += 1; --k; } }
subs[k=1] = 1;
imprime (subs, 1);
while (subs[1] < n) {
if (subs[k] < n) {
subs[k+1] = subs[k] + 1; ++k; }
else {
subs[k-1] += 1; --k; }
imprime (subs, k); }
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 *subs;
subs = malloc ((n+1) * sizeof (int));
ssLexComPrefixo (subs, 0, 1, n);
free (subs);
}
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 subs[], int k, int m, int n)
{
if (m <= n) {
// caso 1: inclui m
subs[k+1] = m;
imprime (subs, k+1);
ssLexComPrefixo (subs, k+1, m+1, n);
// caso 2: não inclui m
ssLexComPrefixo (subs, k, m+1, n);
}
}
(É tentador começar o código da função com
if (m > n) imprime (subs,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 subs[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 subs[1..k].
Em outras palavras, imprime todas as sequências da forma x[1..k..kk] tais que x[1..k] = subs[1..k] e x[k+1..kk] é uma subsequência não vazia de m..n.
Suponha, por exemplo, que subs[1] = 2, subs[2] = 4, e n = 9. Então a chamada ssLexComPrefixo (subs, 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 (subs,3); as três linhas seguintes são produzidas por ssLexComPrefixo (subs, 3, 8, n); e as demais, por ssLexComPrefixo (subs, 2, 8, n).
Portanto, a chamada ssLexComPrefixo (subs, 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 subs[0..n+1]).
A B C AB AC BC ABC
onde ≤
denota a relação
igual ou lexicograficamente menor
.
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.
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
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. Por exemplo, as 24 permutações de 1 2 3 4 são
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
(Aqui, as permutações estão em ordem lexicográfica. Em particular, a primeira permutação é crescente e a última é decrescente.)
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.
A ordem em que as permutações são enumeradas não é muito importante, mas é natural dar preferência à ordem lexicográfica.
Preliminares. A ideia é gerar cada permutação a partir de sua predecessora imediata. Considere, por exemplo, as permutações de 1..4. Para obter a sucessora imediata da permutação 3 4 1 2, podemos apagar o último termo, somar 1 ao penúltimo, e adotar o único valor possível para o último termo:
3 4 1 2 3 4 2 - 3 4 2 1
Em geral, pode ser necessário repetir esse processo. Por exemplo, para obter a sucessora imediata de 2 1 4 2, não basta apagar o último termo, pois o valor seguinte do penúltimo termo não pertence ao universo 1..4. Considere então apagar os dois últimos termos e somar 1 ao antepenúltimo. Isso ainda não resolve o impasse, pois já temos um 2 entre os primeiros termos. Mas somar mais 1 ao antepenúltimo termo torna-o diferente dos anteriores e assim resolve o impasse. Por fim, basta preencher as posições que ficaram vagas com os valores que ainda faltam, 1 e 4, nessa ordem:
2 1 4 3 2 1 5 - não, pois 5 não pertence ao universo 2 2 - - não, porque já temos 2 à esquerda 2 3 - - sim! todos diferentes! 2 3 1 4 completar em ordem crescente
Para dar uma descrição geral do processo, diremos que uma subpermutação de 1..n é qualquer permutação de uma subsequência de 1..n. Em outras palavras, uma subpermutação de 1..n é qualquer vetor perm[1..k] cujos elementos pertencem a 1..n e são diferentes entre si. Agora, o algoritmo pode ser organizado de modo que cada iteração comece com
Cada iteração incorpora m (incrementando k) ou desiste de m, decrementa k, e escolhe um novo m. (Esse movimento de volta, que desfaz o último elemento de perm[1..k] e prepara o valor seguinte de m, é conhecido como backtrack.) Ao cabo de algumas iterações, teremos a sucessora imediata da permutação inicial ou constataremos que não existe sucessora, pois a permutação inicial já é a última.
Segue um esboço do código que realiza a tarefa. Se k == n, já temos uma permutação completa e portanto o único movimento possível é um backtrack:
m = perm[k] + 1; --k;
(Esse processo de fazer-e-desfazer lembra minha avó tricotando um sueter de lã por tentativa-e-erro!) Se k < n, é preciso verificar se m já não está em perm[1..k]:
while (m <= n && !pode (perm, k, m))
m++;
if (m <= n) { // pode
perm[k+1] = m;
m = 1;
++k;
} else {
m = perm[k] + 1;
--k;
}
A função booleana pode com argumentos (perm, k, m) decide se m é diferente dos elementos de perm[1..k].
Algoritmo. O esboço que acabamos de fazer leva à seguinte função de enumeração de permutações:
// Imprime, em ordem lexicográfica, // todas as permutações de 1..n. void permutacoes (int n) { int *perm = malloc ((n+1) * sizeof (int)); int k; for (k = 1; k <= n; k++) perm[k] = k; k = n; while (true) { int m; if (k >= n) { imprime (perm, n); m = n+1; // para forçar backtracking } while (m <= n && !pode (perm, k, m)) m++; if (m <= n) { // pode perm[k+1] = m; m = 1; ++k; } else { // backtrack if (k < 1) break; m = perm[k] + 1; --k; } } free (perm); } // Recebe subpermutação perm[1..k] e decide // se perm[1..k]m é uma subpermutação. static bool pode (int *perm, int k, int m) { for (int i = 1; i <= k; ++i) if (m == perm[i]) return false; return true; }
(Eu admito
que esse código é deselegante
e difícil de entender.
Tente escrever um código melhor!)
Não é necessário começar a primeira iteração
com a permutação 1..n.
Podemos começar com a subpermutação vazia:
basta trocar
for (k = 1; k <= n; k++) perm[k] = k;
k = n;
por
k = 0; m = 1;
.
Para entender o algoritmo,
é preciso descobrir seus invariantes.
Não convém formular os invariantes no início do processo iterativo
mas sim imediatamente depois que uma permutação é impressa,
ou seja,
depois do bloco
if (k >= n) { ... }
.
A cada passagem por esse ponto,
temos um índice k que pertence a 0..n,
um número m
que pertence a 1..n+1, e
uma subpermutação perm[1..k] de 1..n
com a seguinte propriedade:
todas as permutações lexicograficamente menores que perm[1..k]m já foram impressas.
(A expressão perm[1..k]m representa a sequência p[1..k] seguida de um termo com valor m. Essa sequência não é, necessariamente, uma subpermutação.)
A função permutacoes só pode ser usada para valores muito modestos de n, uma vez que o número de permutações cresce assustadoramente à medida que n aumenta.
void permutacoes (int n) {
int *perm;
perm = malloc ((n+1) * sizeof (int));
permsComPrefixo (perm, 0, n);
free (perm);
}
static void permsComPrefixo (int* sp, int i, int n) {
if (i >= n) imprime (sp, n);
else {
for (int m = 1; m <= n; m++) {
if (pode (sp, i, m)) {
sp[i+1] = m;
permsComPrefixo(sp, i+1, n); } } }
}
static bool pode (int *sp, int i, int m) {
for (int k = 1; k <= i; k++)
if (m == sp[k]) return false;
return true;
}
void permutacoes (int n) {
int *perm;
perm = malloc ((n+1) * sizeof (int));
for (int i = 1; i <= n; i++) perm[i] = i;
permsComPrefixo (perm, 0, n);
free (perm);
}
static void permsComPrefixo (int *perm, int i, int n) {
if (i >= n-1)
imprime (perm, n);
else {
for (int j = i+1; j <= n; j++) {
troca (perm, i+1, j);
permsComPrefixo (perm, i+1, n);
troca (perm, i+1, j); } }
}
static void troca (int *perm, int k, int j) {
int t = perm[k]; perm[k] = perm[j]; perm[j] = t;
}
ABC ACB BAC BCA CBA CAB
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.)