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