Python - Backtracking
Il backtracking è una forma di ricorsione. Ma implica la scelta dell'unica opzione tra tutte le possibilità. Iniziamo scegliendo un'opzione e torniamo indietro da essa, se raggiungiamo uno stato in cui concludiamo che questa opzione specifica non fornisce la soluzione richiesta. Ripetiamo questi passaggi esaminando ogni opzione disponibile fino a ottenere la soluzione desiderata.
Di seguito è riportato un esempio di come trovare tutti i possibili ordini di disposizioni di un dato insieme di lettere. Quando scegliamo una coppia, applichiamo il backtracking per verificare se quella coppia esatta è già stata creata o meno. Se non è già stata creata, la coppia viene aggiunta all'elenco delle risposte altrimenti viene ignorata.
def permute(list, s):
if list == 1:
return s
else:
return [ y + x
for y in permute(1, s)
for x in permute(list - 1, s)
]
print(permute(1, ["a","b","c"]))
print(permute(2, ["a","b","c"]))
Quando il codice sopra viene eseguito, produce il seguente risultato:
['a', 'b', 'c']
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']