5

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

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

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

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

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

4

4 回答 4

5

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

考虑您的示例列表

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

有四个孔 ( len(A) + len(B))，您可以在其中放置元素（钉子）

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

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

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

您可以将第二个列表中的元素（钉子）放入钉子的方式数量很简单，您可以从孔中选择插槽的方式数量是

len(A) + len(B)Clen(B)

= 4C2

=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]]
于 2013-03-09T06:11:00.550 回答
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 个组合。

于 2013-03-09T06:03:01.183 回答
1

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

如果您想避免使用封装的神奇优点，我的提示是使用递归。

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

  1. 从第一个列表中取出第一个元素
  2. 从另一个列表中选择第二个或第一个
  3. 要么拿第三名，要么拿第二名，如果你没有，或者从另一个列表中选择另一个
  4. ...

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

玩它。:)

于 2013-03-09T01:56:03.280 回答
0

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

于 2013-03-09T06:08:44.007 回答