Dichiarazione di non responsabilità: il metodo descritto di seguito non è universale, ma spesso può risolvere un problema o aiutarti a trovare la soluzione giusta.
Se hai bisogno di verificare l'esistenza di una permutazione in un problema, o trovare il numero di permutazioni che corrispondono, o qualcosa di simile, allora dovresti prendere in considerazione l'utilizzo della programmazione di sottoinsiemi dinamici.
Il parametro principale sarà una maschera di bit, che mostrerà quali elementi sono già stati inclusi nella permutazione e quali no. Inoltre spesso è richiesto un secondo parametro che indichi quale elemento è stato incluso per ultimo.
Spesso le permutazioni possono essere viste nel contesto dei percorsi nei grafici. Di conseguenza, consideriamo un esempio classico: il problema del percorso hamiltoniano.
Un cammino hamiltoniano è un cammino semplice che attraversa ogni vertice del grafo esattamente una volta. Può essere rappresentato semplicemente come una permutazione di lunghezza n, dove n è il numero di vertici. L'ordine all'interno di questa permutazione indicherà l'ordine in cui vengono attraversati i vertici in questo percorso.
Per verificare la presenza di un percorso hamiltoniano nel grafico, iniziamo la dinamica dp[mask][last] - esiste un percorso semplice che ha aggirato i vertici contrassegnati con quelli nella maschera di bit ed è finito all'ultimo vertice.
I valori iniziali saranno dp[2i][i] = true, il resto false, il che significa che c'è sempre un percorso vuoto che inizia in uno qualsiasi dei vertici.
Avendo il valore true in dp[mask][last] faremo delle transizioni in avanti, nel senso di "estendere il percorso". Cioè, cercheremo i numeri di vertici che sono contrassegnati con zero nella maschera (non li abbiamo ancora visitati per strada) e allo stesso tempo tale che ci sia un bordo dall'ultimo a questo vertice (il percorso deve essere esteso da un bordo esistente). Cioè, facciamo dp[mask | 2k][k] = true se dp[mask][last] = true AND mask & 2k = 0 (il vertice k non è stato ancora visitato) E c'è un ultimo spigolo -> k.
In definitiva, esiste un percorso hamiltoniano se esiste un valore vero in dp per i parametri della maschera di bit tutti uno e per ogni ultimo vertice.