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

I want to create a function that takes in two lists, the lists are not guaranteed to be of equal length, and returns all the interleavings between the two lists.

输入：两个列表不具有相等大小

Input: Two lists that do not have to be equal in size.

输出：二列出了preserve原始列表的顺序之间的所有可能的交错

Output: All possible interleavings between the two lists that preserve the original list's order.

示例： 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]]

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

我不希望有一个解决方案。我想一个暗示。

I do not want a solution. I want a hint.

推荐答案

Itertools不会有足够的能力来处理这个问题，将需要的钉孔和理解问题的一些位

Itertools would not be capable enough to handle this problem and would require some bit of understanding of the pegs and holes problem

考虑您的示例清单

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

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

有四个孔（ LEN（A）+ LEN（B）），您可以将元素（钉）

There are four holes (len(A) + len(B)) where you can place the elements (pegs)

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

在Python中，你可以重新present空槽作为无列表

In Python you can represent empty slots as a list of None

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

办法你可以把从第二个列表中的元素（钉）成数挂钩只是，方式的数量可以从它

The number of ways you can place the elements (pegs) from the second list into the pegs is simply, the number of ways you can select slots from the holes which is

LEN（A）+ LEN（B） C LEN（B）

= 4 C 2

= 4C2

= itertools.combinations（范围（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)   

现在每个这些插槽位置填充它与第二个列表

Now for each of these slot position fill it with elements (pegs) from the second list

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

一旦你完成，你只需要填写剩余的空槽从第一列表中的元素（钉）

Once you are done, you just have to fill the remaining empty slots with the elements (pegs) from the first list

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

在你开始下一次迭代与另一个插槽位置，刷新你的孔

Before you start the next iteration with another slot position, flush your holes

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

一个Python实现为上述方法

A Python implementation for the above approach

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

And the O/P from the above implementation

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