Algoritmos de enumeração

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.

Os problemas de enumeração estão relacionados com termos como backtracking, busca exaustiva, força bruta, e branch-and-bound.

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

  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] .

Nas mesmas condições, 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 .

Num dado conjunto de sequências, uma sequência r é a predecessora imediata de outra, digamos s, se for a maior das sequências menores que s na ordem lexicográfica.  O conceito de sucessora imediata de uma sequência é definido de maneira análoga.

Exercícios 1

  1. Esreva uma função booleana que decida se uma sequência r[1 . . j] é lexicograficamente menor que uma sequência s[1 . . k].

Enumeração de subsequências

Uma subsequência é o que sobra quando alguns termos de uma sequência são apagados.  Mais precisamente, 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 < . . . < ikn 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 uma unidade.

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;
}

Esse cálculo 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 propósito, a operação dentro do bloco else {} é conhecida como backtrack ou volta de ré.

Exercícios 2

  1. Mostre que o número de subsequências de 1 . . n dobra toda vez que n aumenta de uma unidade.  Deduza daí que o número de subsequências de  1 . . n  é  2n.
  2. Escreva uma função que receba uma subsequência subs[1 . . k] de 1 . . n e imprima sua sucessora imediata.

Subsequências em ordem lexicográfica

A discussão da 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);
}

(A instrução imprime (subs, k) não faz mais que imprimir subs[1..k].)  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 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.

Exercícios 3

  1. Que acontece se 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.
  2. No código de ssLex, a variável k pode crescer mas nunca é comparada com n.  Isso não é um erro?
  3. Analise a seguinte versão alternativa de ssLex.
    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; } }
    
  4. Analise a seguinte versão alternativa de ssLex:
    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); }
    
  5. ★ Escreva uma versão da função ssLex que trate o vetor subs[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.
  6. Modifique a função ssLex para que ela produza todas as subsequências não vazias de 0..n-1.
  7. 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.
  8. Two Sum.  Escreva um algoritmo eficiente 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 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 *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);
   }
}

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(É 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.)

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]).

Exercícios 4

  1. Importante.  Verifique, cuidadosamente, a correção do código de ssLexR nos casos em que n vale 0, 12.
  2. Subsequências de 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 subs[1..k] de 1..n é a sequência  b[1..n]  de bits que indica quais dos elementos 1..n estão em subs[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  é  01101 .  Escreva uma função que calcule o vetor característico de uma subsequência subs[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 subs[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. Verifique que a ordem lexicográfica no conjunto de todas as subsequências de 1 . . n é uma ordem total, ou seja, para quaisquer subsequências r e s tem-se
    1.   rs  ou  sr,
    2.   se  rs  e  sr  então  r = s,
    3.   se  rs  e  st  então  rt,

    onde    denota a relação igual ou lexicograficamente menor.

  5. Ordem lexicográfica especial.  A ordem lexicográfica especial dá preferência às subsequências mais longas:  uma sequência r[1 . . j] é menor que outra s[1 . . k] na ordem lexicográfica especial se  (1) existe i tal que r[1 . . i−1] é igual s[1 . . i−1] e r[i] < s[i]  ou  (2) j > k e r[1 . . k] é igual s[1 . . k].  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. [Solução.]

  6. Ordem militar.  As subsequências de 1 . . n podem ser colocadas em ordem militar.  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
    
  7. Bipartição equilibrada.  Dois irmãos receberam uma herança que consiste em n objetos, cada objeto i tendo um 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 (não necessariamente inteiros positivos), encontrar uma subsequência s[1 . . k] de 1 . . n tal que  v[s[1]] + … + v[s[k]]  =  v[t[1]] + … + v[t[m]] ,  sendo t[1 . . m] o complemento de s[1 . . k] em 1 . . n.  Escreva uma função que resolva o problema.
  8. Combinações.  Escreva uma função que imprima todas as subsequências de  1 . . n  que têm exatamente  k  elementos.  (Isso corresponde, exatamente, aos subconjuntos de {1, 2, . . . , n} que têm exatamente k elementos.)

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.  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, 14, 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 (aumentando k) ou desiste de m, reduz 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 x[1..k+1] tal que x[1..k] é igual a perm[1..k] e x[k+1] == 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.

Exercícios 5

  1. Prove que há exatamente  n!  permutações de 1 . . n.
  2. Importante.  Verifique, cuidadosamente, a correção do código de permutacoes nos casos em que n vale 0, 12.
  3. Escreva uma função que receba uma permutação perm[1..n] de 1..n e imprima sua sucessora imediata.
  4. Versão recursiva.  Analise a seguinte versão da função permutacoes, que enumera as permutações de 1..n em ordem lexicográfica.  O que faz, exatamente, a função recursiva permsComPrefixo?
    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; 
                comprefixo (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; 
    }
    
  5. Um algoritmo clássico.  Analise o seguinte algoritmo 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 *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; 
    }
    
  6. Permutação de cadeias de caracteres.  Escreva uma função que imprima todas as permutações dos bytes 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 
    
  7. Problema das rainhas.  É possível colocar 8 rainhas do jogo de xadrez sobre o tabuleiro de modo que nenhuma das rainhas possa atacar outra?  Escreva uma função que enumere todas as maneiras de dispor n rainhas num tabuleiro generalizado n×n.  Uma disposição das rainhas pode ser representada por um vetor perm[1 . . n] tal que a rainha da linha i fica na coluna perm[i].  (Sugestão: Adapte o código da função permutacoes.)
  8. 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 complete um passeio por todas as n×n posições do tabuleiro em n×n − 1 passos válidos. 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.)

  9. Permutação circular.  Uma sequência s[1 . . n] é permutação circular de outra t[1 . . n] se existe k tal que s[k . . n] é igual a t[1 . . nk+1] e s[1 . . k−1] é igual a t[nk+2 . . n].  Escreva uma função que decida se s[1 . . n] é permutação circular de t[1 . . n].
  10. 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.
  11. Distância tau de Kendall.  Como medir a distância entre duas permutações?  Veja exercício no capítulo do algoritmo Mergesort.
  12. 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] é diferente de 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, exatamente uma vez, cada desarranjo de 1..n.
  13. 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.