Python-バックトラッキング

バックトラッキングは再帰の一種です。ただし、可能性のあるオプションのみを選択する必要があります。この特定のオプションでは必要な解決策が得られないと結論付けられる状態に達した場合、オプションを選択し、そこからバックトラックします。目的のソリューションが得られるまで、使用可能な各オプションを調べて、これらの手順を繰り返します。

以下は、与えられた文字セットの配置のすべての可能な順序を見つける例です。ペアを選択すると、バックトラックを適用して、その正確なペアがすでに作成されているかどうかを確認します。まだ作成されていない場合、ペアは回答リストに追加され、そうでない場合は無視されます。

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

上記のコードが実行されると、次の結果が生成されます-

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

Python-data-structure-python-backtracking

Python-バックトラッキング