如何计算两个列表的所有交错？

Question

我想创建一个接受两个列表的函数，不能保证列表的长度相等，并返回两个列表之间的所有交错。在

输入：两个大小不必相等的列表。在

输出：保留原始列表顺序的两个列表之间所有可能的交错。在

示例：ALINTER（[1,2]，[3,4]）->；[[1,2,3,4]，[1,3,2,4]，[1,3,4,2]，[3,1,2,4]，[3,4,1,2]]

我不想要一个解决办法。我想要个暗示。在

Answer 1

正如@airza建议的，itertools模块是您的朋友。在

如果你想避免使用封装的魔法善，我的建议是使用递归。在

开始在脑海中播放生成列表的过程，当你注意到你又在做同样的事情时，试着找出模式。例如：

1. 从第一个列表中获取第一个元素
2. 从另一个列表中选择第二个或第一个
3. 要么选第三个，如果没有，就选第二个，或者从另一个单子里选一个
4. 。。。在

好吧，看来我们没有使用更合理的逻辑了。我只是在增加数字。当然，我可以找到一个在更改“第一个元素，而不是命名更高的元素”时起作用的基本情况吗？在

玩玩它。：）

Answer 2

Itertools不足以处理这个问题，需要对peg和holes问题有一些了解

考虑您的示例列表

A=[1，2] B=[3，4]

有四个孔（len(A) + len(B)）可以放置元素（木桩）

|   ||   ||   ||   |
|___||___||___||___|

在Python中，可以将空槽表示为None的列表

^{pr2}$

您可以将第二个列表中的元素（peg）放置到pegs中的方法非常简单，您可以从孔中选择插槽的方法是

^{len(A) + len(B)}C_len(B)

=⁴C₂

=itertools.combinations(range(0, len(len(A) + len(B)))

可以描述为

^{3}$

现在，对于每个插槽位置，用第二个列表中的元素（peg）填充它

for splice in combinations(range(0,len(slots)),len(B)):
    it_B = iter(B)
    for s in splice:
        slots[s] = next(it_B)

完成后，您只需使用第一个列表中的元素（peg）填充剩余的空插槽

    it_A = iter(A)
    slots = [e if e else next(it_A) for e in slots]

在使用另一个插槽位置开始下一次迭代之前，请冲洗孔

    slots = [None]*(len(slots))

上述方法的Python实现

def slot_combinations(A,B):
    slots = [None]*(len(A) + len(B))
    for splice in combinations(range(0,len(slots)),len(B)):
        it_B = iter(B)
        for s in splice:
            slots[s] = next(it_B)
        it_A = iter(A)
        slots = [e if e else next(it_A) for e in slots]
        yield slots
        slots = [None]*(len(slots))

以及上述实现的O/p

list(slot_combinations(A,B))
[[3, 4, 1, 2], [3, 1, 4, 2], [3, 1, 2, 4], [1, 3, 4, 2], [1, 3, 2, 4], [1, 2, 3, 4]]

Answer 3

提示：假设每个列表都有相同的元素（但是列表之间的元素不同），即一个列表是完全红色的（比如r），另一个列表是蓝色的（比如b）。在

输出的每个元素包含r+b或它们，其中r为红色。在

似乎其他人已经为你毁了它，即使你没有要求一个解决办法（但他们有一个很好的解释）

我很快写下了代码。在

import itertools

def interleave(lst1, lst2):
    r,b = len(lst1), len(lst2)
    for s in itertools.combinations(xrange(0,r+b), r):
        lst = [0]*(r+b)
        tuple_idx,idx1,idx2 = 0,0,0
        for i in xrange(0, r+b):
            if tuple_idx < r and i == s[tuple_idx]:
                lst[i] = lst1[idx1]
                idx1 += 1
                tuple_idx += 1
            else: 
                lst[i] = lst2[idx2]
                idx2 += 1
        yield lst


def main():
    for s in interleave([1,2,3], ['a','b']):
        print s

if __name__ == "__main__":
    main()

基本思想是将输出映射到（r+b）choose r组合。在