python - 交错两个字符串的所有可能方法

Question

我正在尝试生成所有可能的方式来在 Python 中交错任意两个任意字符串。

例如:如果两个字符串分别是'ab'和'cd'，我希望得到的输出是:

['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']

请参见 a 总是在 b 之前(并且 c 在 d 之前)。我正在努力寻找解决方案。我已经尝试过如下所示的 itertools:

import itertools

def shuffle(s,t):
    string = s+t
    for i in itertools.permutations(string):
        print(''.join(i))

shuffle('ab','cd')

但正如预期的那样，这将返回所有可能的排列，而不管 a 和 b (以及 c 和 d)。

Answer 1

理念

让你想要交错的两个字符串是 s 和 t。我们将使用递归来生成所有可能的方式来交错这两个字符串。

如果在任何时候我们已经交错了 s 的前 i 字符和 t< 的前 j 字符 来创建一些字符串 res，那么我们有两种方法可以将它们交错以进行下一步-

1. 将 s 的第 i+1 个字符附加到 res
2. 将 t 的第 j+1 个字符附加到 res

我们继续这个递归，直到两个字符串的所有字符都被使用，然后我们将这个结果存储在字符串列表 lis 中，如下面的代码所示。

代码

def interleave(s, t, res, i, j, lis):
    if i == len(s) and j == len(t):
        lis.append(res)
        return
    if i < len(s):
        interleave(s, t, res + s[i], i + 1, j, lis)
    if j < len(t):
        interleave(s, t, res + t[j], i, j + 1, lis)

l = []
s = "ab"
t = "cd"
interleave(s, t, "", 0, 0, l)
print l

输出

['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']

这个实现是尽可能高效的(至少是渐近的)，因为我们不会两次生成相同的字符串。