python - Python での文字列の制限された順列

Question

Pythonで次のことを行うにはどうすればよいですか?

与えられた 2 つの文字列。2 つの文字列のインターリーブをすべて出力します。インターリーブとは、B が A の後に来る場合、インターリーブされた文字列で A の後にも来る必要があることを意味します。ex- AB および CD ABCD ACBD ACDB CABD CADB CDAB

Answer 1

これは事実上、ツリーウォーキングの問題です（つまり、一方のストリングに沿って進むか、もう一方のストリングに沿って進むかどうかの決定木）。多くの場合、ツリーウォーキングの問題に取り組む最も簡単な方法は再帰的な解決策です。

---

次に例を示します。

def ordered_permutations(str1, str2):
    perms = []
    if len(str1) + len(str2) == 1:
        return [str1 or str2]
    if str1:
        for item in ordered_permutations(str1[1:], str2):
            perms.append(str1[0] + item)
    if str2:
        for item in ordered_permutations(str1, str2[1:]):
            perms.append(str2[0] + item)
    return perms

Answer 2

問題を認識し、非常に洗練された解決策を提供してくれた@Amberに敬意を表します。

これが私の2セントの価値です（答えを印刷するだけです）：

def interleave(L1, L2, answer=None):
    if answer is None:
        answer = ''
    if not L1 and not L2:
        print answer
    else:
        if L1:
            a = answer + L1[0]
            interleave(L1[1:], L2, a)
        if L2:
            ans = answer + L2[0]
            interleave(L1, L2[1:], and)

>>> interleave('ab', 'cd')
abcd
acbd
acdb
cabd
cadb
cdab

お役に立てれば