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

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

Input:两个列表的大小不必相等。

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

Example: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]]

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

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