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