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

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

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

- user810606

---

好的，我会尽力进行翻译。以下是需要翻译的内容：hint: import itertools - argentage

那是一个惊人的提示。 - salezica

我的Python列表问题大多数都是通过记住它的存在而得以解决的。 - argentage

当然。而且大多数没有被itertools解决的问题都可以通过查看其文档中的示例来解决。 - abarnert

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

以下是上述实现的输出结果：

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

- Abhijit

---

这里有一个更懒的（它使用生成器而不是子列表）解决钉和孔问题的方案：interleave_where()。 - jfs

啊，我们得到了完整的实现，而不是提示。很好。 - nneonneo

很好的解释。你本可以只说我的问题是钉孔问题的一个实例，而不必提供实现。在我接受你的答案之前，你能否校对一下它（我认为解释中有一些错别字。应该是= itertools.combinations(range(0, len(A) + len(B)), 2)吧？）并提供“钉孔问题”的前提条件？我尝试过谷歌搜索，但只找到了“方钉圆孔”之类的问题。如果你提供一个好的前提条件，我甚至会建议你删除实现部分，但这是你的选择。 - user810606

Answer 2

提示：假设每个列表都有相同的元素（但在列表之间不同），即一个列表完全为红色（例如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)个中选择r个组合。

- Knoothe

Answer 3

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

如果您想避免使用封装的神奇功能，则可以尝试使用递归。

开始在脑海中玩生成列表的过程，当您注意到自己再次执行相同操作时，尝试找到模式。例如：

1. 从第一个列表中取出第一个元素
2. 从另一个列表中取第2个元素或第1个元素
3. 如果您没有取第2个元素，则从第一个列表中取第3个元素或从另一个列表中取另一个元素
4. ...

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

尝试一下。 :)

- salezica

Answer 4

如果你想更接近底层且更优雅（在我看来），可以尝试迭代不同的可能切片。基本上，通过标准切片操作遍历和迭代所有三个参数，删除添加到最终列表中的任何内容。如果您有兴趣，可以发布代码片段。

- Slater Victoroff