Isenção de responsabilidade: o método descrito abaixo não é universal, mas muitas vezes pode resolver um problema ou ajudá-lo a encontrar a solução certa.
Se você precisa verificar a existência de uma permutação em um problema, ou encontrar o número de permutações que correspondem, ou algo similar, então você deve considerar o uso da programação dinâmica de subconjuntos.
O parâmetro principal será uma máscara de bits, que mostrará quais elementos já foram incluídos na permutação e quais não foram. Muitas vezes também é necessário um segundo parâmetro que indica qual elemento foi incluído por último.
Freqüentemente, as permutações podem ser vistas no contexto de caminhos em gráficos. Assim, consideremos um exemplo clássico - o problema do caminho hamiltoniano.
Um caminho hamiltoniano é um caminho simples que passa por cada vértice do grafo exatamente uma vez. Pode ser representado simplesmente como uma permutação de comprimento n, onde n é o número de vértices. A ordem dentro desta permutação indicará a ordem na qual os vértices neste caminho são percorridos.
Para verificar a presença de um caminho hamiltoniano no grafo, vamos iniciar a dinâmica dp[mask][last] - existe um caminho simples que contornou os vértices marcados com uns no bitmask da máscara e acabou no último vértice.
Os valores iniciais serão dp[2i][i] = verdadeiro, o resto falso, o que significa que sempre há um caminho vazio começando em qualquer um dos vértices.
Tendo o valor true em dp[mask][last] faremos as transições para frente, no sentido de "estender o caminho". Ou seja, procuraremos o número de vértices marcados com zero na máscara (ainda não os visitamos no caminho) e ao mesmo tempo de forma que haja uma aresta do último a este vértice (o caminho deve ser estendido por uma aresta existente). Ou seja, fazemos dp[mask | 2k][k] = true if dp[mask][last] = true AND mask & 2k = 0 (o vértice k ainda não foi visitado) E há uma última aresta -> k.
Por fim, existe um caminho hamiltoniano se houver um valor verdadeiro em dp para os parâmetros da bitmask de todos os uns e qualquer último vértice.