Gerando todas as permutações de um conjunto

Lá pelo segundo ano do ensino médio costumam ensinar aos alunos como calcular o número de combinações e permutações possíveis em um conjunto. O número de permutações é relativamente simples: dado um conjunto A={a1, a2, a3 … aN} com N elementos temos para o primeiro elemento das permutações N possibilidades, para o segundo (N-1) e assim por diante. Então o número de permutações possíveis é N! (N fatorial).

Ok, sabemos quantas permutações são possíveis. Agora, outra coisa é gerar todas estas permutações.

Algoritmo para gerar todas as permutações de um conjunto

Imagine um conjunto A={a, b, c}. Bem simples. Uma forma de visualizar o processo de obtenção das permutações é através de uma árvore.

Cada vez que descemos um galho na árvore, eliminamos um elemento do conjunto do nó acima. Desta maneira, quando chegamos na camada mais baixa, quando só se tem um elemento em cada nó, terminamos a árvore. Melhor ainda, podemos descer, como na figura, respeitando a ordem alfabética, assim vamos ter todas as permutações em ordem lexicográfica (a mesma do dicionário). Para recuperar as permutações, só temos que contar desde cada nó final os elementos com os quais descemos a árvore (é mais fácil olhar a figura).

Assim temos (a,b,c); (a,c,b); (b,a,c); (b,c,a); (c,a,b); (c, b, a).

Agora que já sabemos o que queremos fazer, podemos escrever um algoritmo pra fazer isso pra uma quantidade maior de números.

A forma mais fácil de reproduzir este método é através de recursão, mais precisamente com Backtracking. Somente temos que chamar constantemente uma função que elimina um elemento do nosso conjunto (e o guarda em uma lista) cada vez que descemos um galho. O algoritmo foi escrito em JavaScript.

Rodando o algoritmo para um set {A, B, C, D}, temos:

[
  [ 'D', 'C', 'B', 'A' ], [ 'C', 'D', 'B', 'A' ],
  [ 'D', 'B', 'C', 'A' ], [ 'B', 'D', 'C', 'A' ],
  [ 'C', 'B', 'D', 'A' ], [ 'B', 'C', 'D', 'A' ],
  [ 'D', 'C', 'A', 'B' ], [ 'C', 'D', 'A', 'B' ],
  [ 'D', 'A', 'C', 'B' ], [ 'A', 'D', 'C', 'B' ],
  [ 'C', 'A', 'D', 'B' ], [ 'A', 'C', 'D', 'B' ],
  [ 'D', 'B', 'A', 'C' ], [ 'B', 'D', 'A', 'C' ],
  [ 'D', 'A', 'B', 'C' ], [ 'A', 'D', 'B', 'C' ],
  [ 'B', 'A', 'D', 'C' ], [ 'A', 'B', 'D', 'C' ],
  [ 'C', 'B', 'A', 'D' ], [ 'B', 'C', 'A', 'D' ],
  [ 'C', 'A', 'B', 'D' ], [ 'A', 'C', 'B', 'D' ],
  [ 'B', 'A', 'C', 'D' ], [ 'A', 'B', 'C', 'D' ]
]