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

Question

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

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

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

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

看到代码中 a 始终在 b 之前 (并且 c 在 d 之前)。我正在努力寻找解决方案。我已经尝试过以下方法：

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）的顺序。

- Seb

---

相关链接：http://codegolf.stackexchange.com/questions/76428/all-possible-ways-to-interleave-two-strings - DJMcMayhem

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

这个实现尽可能地高效（至少在渐近意义下），因为我们从不生成相同的字符串两次。

- Banach Tarski

---

根据上下文，您可能希望消除递归结构或实现Pythonic尾递归。请参见https://dev59.com/NmYr5IYBdhLWcg3wi6zd。 - Adam Martin

这个实现在渐进意义下是尽可能高效的。但是，如果存在重复项，则不是这样。您应该将部分字符串存储在Trie或哈希表中，以防止重复工作。 - Neil G

能否在不使用数组/排序的情况下按字典顺序打印结果？ - Jey Raj

Answer 2

已经发布了几种其他的解决方案，但它们中的大多数都会在内存中生成交错字符串的完整列表（或等效物），使得随着输入长度的增加，它们的内存使用量呈指数级增长。肯定有更好的方法。

枚举两个长度分别为a和b的序列交错的所有方式基本上相当于枚举所有具有a+b位并恰好有b位设置为1的二进制数。每个这样的整数对应于一种不同的交错顺序，通过将每个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中工作。

- Ilmari Karonen

---

非常聪明。你可能会对我今天写的一个东西感兴趣，它（如果我正确使用Python术语）以合理的时间限制交错两个生成器。只有在生成器最终停止时，它才能保证产生所有可能的方式，但这似乎是为了效率而付出的合理代价。 - dfeuer

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"))

- JeD

Answer 4

您只需要比较a的索引与b的索引，以及c的索引与d的索引，然后过滤掉那些a的索引大于b的索引且c的索引大于d的索引的元素。

def interleave(s, t):
    mystring = s + t
    return [el for el in [''.join(item) for item in permutations(mystring) if  item.index('a') < item.index('b') and item.index('c') < item.index('d')]]

演示：

>>> from itertools import permutations
>>> s = 'ab'
>>> t = 'cd'
>>> [el for  el in [''.join(item) for item in permutations(s+t) if item.index('a') < item.index('b') and item.index('c') < item.index('d')]]
['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']

- styvane

Answer 5

只是为了运动

一个没有明确条件或谓词的解决方案

（即，没有任何if关键字）：

from itertools import chain, repeat, permutations
from copy import deepcopy


def shuffle(*strings):
    # Treat the strings as pools from which to draw elements in order.
    # Convert the strings to lists, so that drawn items can be removed:
    pools = (list(string) for string in strings)

    # From each pool, we have to draw as many times as it has items:
    pools_to_draw_from = chain.from_iterable(
        repeat(pool, len(pool)) for pool in pools
    )

    # Because itertools.permutations treats elements as unique based on their
    # position, not on their value and because pools_to_draw_from has repeated
    # repeated items, we would get repeated permutations, if we would not
    # filter them out with `unique`.
    possible_drawing_orders = unique(permutations(pools_to_draw_from))

    # For each drawing order, we want to draw (and thus remove) items from our
    # pools. Subsequent draws within the same drawing order should get the
    # respective next item in the pool, i.e., see the modified pool. But we don't
    # want the pools to be exhausted after processing the first drawing ordering.
    #
    # Deepcopy preserves internal repetition and thus does exactly what we need.
    possible_drawing_orders = (deepcopy(pdo) for pdo in possible_drawing_orders)

    # Draw from the pools for each possible order,
    # build strings and return them in a list:
    return [''.join(_draw(p)) for p in possible_drawing_orders]


def _draw(drawing_order):
    return (pool_to_draw_from.pop(0) for pool_to_draw_from in drawing_order)

我们需要一个辅助函数来完成这个任务：

from operator import itemgetter
from itertools import groupby

def unique(iterable, key=None):
    # Other than unique_everseen from
    # https://docs.python.org/3/library/itertools.html#itertools-recipes, this
    # works for iterables of non-hashable elements, too.
    return unique_justseen(sorted(iterable, key=key), key)


def unique_justseen(iterable, key=None):
    """
    List unique elements, preserving order. Remember only the element just seen.
    """
    # from https://docs.python.org/3/library/itertools.html#itertools-recipes
    return map(next, map(itemgetter(1), groupby(iterable, key)))

如果非唯一排列的数量很大，由于调用了sorted，这可能相当低效。要获取具有唯一值的非唯一排列的替代方法，请参见permutations with unique values。

TL;DR?

没问题。我们可以把这种方法简化为这个怪物：

from itertools import chain, repeat, permutations
from copy import deepcopy

def shuffle(*strings):
    return list({''.join(l.pop(0) for l in deepcopy(p)) for p in permutations(chain.from_iterable(repeat(list(s), len(s)) for s in strings))})

（在结果上使用集合推导式而不是早期确保唯一性。）

- das-g

---

天啊，我从没见过在列表推导式中嵌套三个for循环。ಠ_ಠ你真的是疯了。 - cat