我想创建一个接收两个列表的函数,这些列表不保证长度相等,并返回两个列表之间的所有交错。
输入:两个大小不必相等的列表。
输出:保留原始列表顺序的两个列表之间的所有可能交错。
示例: 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)
Clen(B)
= 4
C2
=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]]
提示:假设每个列表具有相同的元素(但列表之间不同),即一个列表完全是红色的(比如其中的 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 个组合。
正如@airza 所建议的那样,该itertools
模块是您的朋友。
如果您想避免使用封装的神奇优点,我的提示是使用递归。
开始在你的脑海中播放生成列表的过程,当你注意到你又在做同样的事情时,试着找到模式。例如:
好的,这开始看起来我们没有使用一些更大的逻辑。我只是增加数字。当然,我可以找到一个在更改“第一个元素而不是命名更高元素”时有效的基本案例?
玩它。:)
你可以尝试一些更接近金属的东西,更优雅(在我看来)迭代不同的可能切片。基本上逐步遍历并遍历标准切片操作的所有三个参数,删除添加到最终列表中的任何内容。如果您有兴趣,可以发布代码片段。