Python - Retour en arrière

Le retour en arrière est une forme de récursivité. Mais cela implique de ne choisir qu'une option parmi toutes les possibilités. Nous commençons par choisir une option et en revenons en arrière, si nous atteignons un état où nous concluons que cette option spécifique ne donne pas la solution requise. Nous répétons ces étapes en parcourant chaque option disponible jusqu'à ce que nous obtenions la solution souhaitée.

Vous trouverez ci-dessous un exemple de recherche de tous les ordres possibles d'arrangements d'un ensemble de lettres donné. Lorsque nous choisissons une paire, nous appliquons un retour en arrière pour vérifier si cette paire exacte a déjà été créée ou non. Si elle n'est pas déjà créée, la paire est ajoutée à la liste de réponses sinon elle est ignorée.

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"]))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

['a', 'b', 'c']
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']