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

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.我们将使用递归来生成交错这两个字符串的所有可能方法.

如果在任何时候我们交错了第一个i字符s和第一个j字符t来创建一些字符串res,那么我们有两种方法可以将它们交错用于下一步 -

1. 追加i+1的个字符s来res
2. 追加j+1的个字符t来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']

这个实现和我们可以获得的效率一样高(至少渐近),因为我们从不生成两次相同的字符串.

Answer 2

已经发布了其他几个解决方案,但是大多数解决方案都会在内存中生成交错字符串(或其等价物)的完整列表,从而使其内存使用量随输入长度呈指数增长.当然必须有更好的方法.

枚举所有的方式来交织长度的两个序列,一个和b分别是基本相同枚举所有一个 + b位整数与exably b的位.每个这样的整数对应于交错序列的不同方式,通过用第一序列的元素替换每0位而获得,并且每1位用第二序列的元素替换.

方便的是,有一种聪明而有效的方法来计算具有相同位数的下一个整数,我们可以使用它来生成所有这样的整数.所以我们先做到这一点:

def bit_patterns(m, n):
    """Generate all m-bit numbers with exactly n bits set, in ascending order.
    See http://www.geeksforgeeks.org/next-higher-number-with-same-number-of-set-bits/
    """
    patt = (1 << int(n)) - 1
    if patt == 0: yield 0; return  # loop below assumes patt has at least one bit set!
    while (patt >> m) == 0:
        yield patt
        lowb = patt & -patt  # extract the lowest bit of the pattern
        incr = patt + lowb   # increment the lowest bit
        diff = patt ^ incr   # extract the bits flipped by the increment
        patt = incr + ((diff // lowb) >> 2)  # restore bit count after increment

现在我们可以使用这个生成器生成交错任意两个序列的所有方法:

def interleave(a, b):
    """Generate all possible ways to interleave two sequences."""
    m = len(a) + len(b)
    n = len(a)
    for pattern in bit_patterns(m, n):
        seq = []
        i = j = 0
        for k in range(m):
            bit = pattern & 1
            pattern >>= 1
            seq.append(a[i] if bit else b[j])
            i += bit
            j += 1-bit
        yield seq

请注意,为了尝试尽可能通用,此代码采用任意序列类型并返回列表.字符串是Python中的序列,因此您可以很好地传递它们; 要将生成的列表转换回字符串,您可以连接它们的元素,例如"".join():

foo = "ABCD"
bar = "1234"
for seq in interleave(foo, bar):
    print("".join(seq))

我们去了:一个完全非递归有效的基于发生器的解决方案,即使对于长输入也只使用很少的内存,并且只生成一次输出(因此不需要低效的重复消除步骤).它甚至适用于Python 2和3.

Answer 3

效率极低但工作:

def shuffle(s,t):
    if s=="":
        return [t]
    elif t=="":
        return [s]
    else:
        leftShuffle=[s[0]+val for val in shuffle(s[1:],t)]
        rightShuffle=[t[0]+val for val in shuffle(s,t[1:])]
        leftShuffle.extend(rightShuffle)
        return leftShuffle

print(shuffle("ab","cd"))