python - Restricted Permutations of Strings in Python

Question

How can I do the following in Python?

Given two strings. Print all the interleavings of the two strings. Interleaving means that the if B comes after A, it should also come after A in the interleaved string. ex- AB and 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 致敬，感谢他发现了问题并给出了非常优雅的解决方案。

这是我的两分钱（只是打印出答案）：

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

希望这可以帮助