我希望在给定大小为n的数组的情况下生成所有可能的4元组对的列表. n至少为8,因此总能找到至少1对.
作为一个有助于理解问题的例子,我使用较小版本的问题,2元组对给出一个大小为5的数组.2元组对的预期结果将导致15个项目(元组被排序,没有重复) ：
[(1,2),(3,4)],[(1,5)],(4,3),( 2,(2,4),3)],[( 1,5),[(2,4)]
我目前的方法是使用python中的itertools并遍历itertools.combinations返回的所有元素,执行2个循环并找到不共享单个元素的2对然后使用该元素.
为了在python代码中表达这一点,我准备了一个小片段：
arr = list(range(30)) # example list
comb = list(itertools.combinations(range(0,len(arr)),4))
for c1 in comb:
for c2 in comb: # go through all possible pairs
if len([val for val in c1 if val in c2]) == 0: # intersection of both sets results in 0,so they don't share an element
... # do something and check for duplicates
此方法正在完成其工作,但由于2个循环而效率低,并且仅在给定时间范围内适用于小n.这可以更有效率吗？
更新：在一些答案后,我评估了建议.对于我的特定情况,最好的事情是MSeifert的(现已删除的)答案提供的(扩展)算法,它执行速度最快：
def generate_four_pairs(n):
valids = range(0,n)
for x00,x01,x02,x03,x10,x11,x12,x13 in itertools.combinations(valids,8):
yield [x00,x03],[x10,x13]
yield [x00,x10],[x03,x11],x12],x13],x12]
yield [x00,[x02,x11]
yield [x00,[x01,x10]
yield [x01,x00],x13]
yield [x01,[x00,x12]
yield [x01,x11]
yield [x01,x13,x11]
对于一般方法,我建议NPE提供的答案,因为这是这个问题的最简单和最简单的可读答案.
最佳答案
你通过生成所有组合对来做了很多不必要的工作,然后丢弃几乎所有组合,因为它们包含共同的元素.
下面通过首先获取四个数字的所有子集(在您的2元组示例中),然后将每个子集分成所有可能的对来解决此问题：
import itertools
def gen_pairs(n,m):
for both_halves in itertools.combinations(xrange(1,n + 1),2 * m):
for first_half in itertools.combinations(both_halves,m):
second_half = tuple(sorted(set(both_halves) - set(first_half)))
yield [first_half,second_half]
print sorted(gen_pairs(5,2))
请注意,这并不能消除重复(例如,[(4,5)(2,3)] vs [(2,5)])因此会产生两倍于您期望的元素数量.
然而,删除重复项是微不足道的.这留给读者练习.