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

Question

我想创建一个接收两个列表的函数,列表不保证长度相等,并返回两个列表之间的所有交错.

输入:两个不必大小相同的列表.

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

示例: AllInter([1,2],[3,4]) - > [[1,2,3,4],[1,3,2,4],[1,3,4,2],[ 3,1,2,4],[3,1,4,2],[3,4,1,2]]

我不想要解决方案.我想要一个提示.

Answer 1

Itertools不足以处理这个问题,并且需要对栓钉和孔问题有一些了解

考虑您的示例列表

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

有四个孔(len(A) + len(B)),你可以放置元素(钉)

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

在Python中,您可以将空插槽表示为列表 None

slots = [None]*(len(A) + len(B))

您可以将从第二个列表中的元素(桩)放入栓钉的方式的数量很简单,您可以从孔中选择槽的方式的数量是

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

= ⁴C.₂

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

可以描述为

|   ||   ||   ||   |  Slots
|___||___||___||___|  Selected

  3    4              (0,1)
  3         4         (0,2)
  3              4    (0,3) 
       3    4         (1,2) 
       3         4    (1,3)
            3    4    (2,3)   

现在,对于每个槽位置,用第二个列表中的元素(桩)填充它

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]

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

    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 2

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

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

开始在你的脑海中玩生成列表的过程，当你注意到你再次做同样的事情时，尝试找到模式。例如：

1. 从第一个列表中取出第一个元素
2. 要么取第二个，要么取另一个列表中的第一个
3. 要么选择第三个，要么选择第二个（如果没有），或者从其他列表中选择另一个
4. ...

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

玩它。:)