我可以使用itertools中的combinations函数生成所有的2元组,但我不知道如何生成所有的23个项目的配对。请问该如何实现或是否有示例代码可供参考?
>>> L=range(46)
>>> def f(x, y): #for example
... return x * y
...
>>> [f(x, y) for x, y in zip(*[iter(L)] * 2)]
[0, 6, 20, 42, 72, 110, 156, 210, 272, 342, 420, 506, 600, 702, 812, 930, 1056, 1190, 1332, 1482, 1640, 1806, 1980]
编辑:
对于幂集的成对元素,我们以相同方式创建成对元素。对于Python3,请使用range
代替xrange
。
S = zip(*[iter(L)] * 2) # set of 23 pairs
[{j for i, j in enumerate(S) if (1<<i)&k} for k in xrange(1<<len(S))]
这将是一个相当大的列表,您可能希望使用生成器表达式
for item in ({j for i, j in enumerate(S) if (1<<i)&k} for k in xrange(1<<len(S))):
func(item)
zip(*[iter(L)] * 2)
如何工作的人:https://dev59.com/0XE95IYBdhLWcg3wm_Mu,而且 是 一个被接受的 Python 習慣用法(不要抱怨它不符合 Python 風格):http://docs.python.org/2/library/functions.html#zip - jamylakset([(0,2), (1,3), (4,5)])
这样的配对,同时也会生成不完整的配对。我宁愿有一个能够回答所提出问题的算法(适用于小N),其阶乘运行时间比一个不能回答问题的解决方案更好。此外,阶乘运行时间并不那么糟糕,特别是由于解决方案大小随着O(N!)增长而渐进地最优。 - dr jimbob首先,从列表中获取所有配对的自然方法是:
>>> N = 10
>>> input_list = range(N)
>>> [(a,b) for a, b in zip(input_list[::2], input_list[1::2])]
[(0, 1), (2, 3), (4, 5), (6, 7), (8, 9)]
>>> set_of_all_pairs = set()
>>> input_list = range(N)
>>> import itertools
>>> for perm in itertools.permutations(input_list):
pairs = tuple([(a,b) for a, b in zip(perm[::2], perm[1::2])])
set_of_all_pairs.add(pairs)
考虑到这个“as is”会区分一对中的顺序(例如,(1,4)与(4,1)是不同的),并且认为一对的顺序具有意义。因此,如果在将一对添加到集合之前对这些对进行排序和去重:
>>> set_of_all_pairs = set()
>>> input_list = range(N)
>>> import itertools
>>> for perm in itertools.permutations(input_list):
pairs = sorted([tuple(sorted((a,b))) for a, b in zip(perm[::2], perm[1::2])])
set_of_all_pairs.add(tuple(pairs))
这不是一个高效的算法(我称之为下面的Case 3),但对于较小的N值,它可以工作。
对于N=6,使用排序方法。
set([((0, 4), (1, 3), (2, 5)),
((0, 4), (1, 5), (2, 3)),
((0, 1), (2, 3), (4, 5)),
((0, 3), (1, 5), (2, 4)),
((0, 2), (1, 5), (3, 4)),
((0, 4), (1, 2), (3, 5)),
((0, 3), (1, 4), (2, 5)),
((0, 1), (2, 4), (3, 5)),
((0, 5), (1, 4), (2, 3)),
((0, 5), (1, 2), (3, 4)),
((0, 2), (1, 3), (4, 5)),
((0, 3), (1, 2), (4, 5)),
((0, 2), (1, 4), (3, 5)),
((0, 1), (2, 5), (3, 4)),
((0, 5), (1, 3), (2, 4))])
请注意解决方案空间的增长速度呈指数增长; (例如,对于N = 6,它的值为15; N = 8,它为105; N = 10,它为945,对于N = 46 将是25373791335626257947657609375〜2.5 x 10 28 )。
问题要求将N个元素的列表(假设所有元素都是不同的最一般情况)分成(N/2)对,并且不仅要执行一次,而是生成所有这些配对的集合。 这个答案是唯一能够做到这一点的答案。 是的,它的速度指数级缓慢,并且对于N = 46来说完全不可行。 这就是为什么我使用N = 10的原因。
问题有三种合理的解释:
情况1:在元组中,顺序对于配对的数字很重要(例如,函数参数不对称),而且在一组配对中,对于配对的顺序也很重要,那么我们将有N!种方法来配对我们答案中的数字。这意味着在这种情况下,配对(0,1)和(1,0)都被认为是不同的,对于N=4的情况,我们认为配对{(0,1), (2,3)}
与{(2,3),(0,1)}
不同。
情况2:在配对中,顺序很重要,但在一组配对中,顺序无关紧要。这意味着我们认为(0,1)和(1,0)是不同的配对,但是认为(对于N=4的情况)集合{(0,1),(2,3)}
与集合{(2,3), (0,1)}
相同,因此不需要考虑两者。在这种情况下,我们将有N!/(N/2)!种配对方式,因为任何给定的集合都有(N/2)!不同的排序方式。(我没有明确说明上面的内容;但只需停止对元组进行排序即可)。
情况3:对于一对数和一组配对,顺序都是无关紧要的。这意味着我们将(0,1)和(1,0)视为同一对(函数参数是对称的),因此我们将有N!/( (N/2)! & 2^(N/2) )个配对集合(factorial(N)/(factorial(N/2)*2**(N/2))
)。每个组合中的(N/2)对都有两个内部排序会产生贡献。
因此,根据问题的陈述方式,我们应该有:
Case 1 | Case 2 | Case 3
----------------------------------------------
N N! | N!/(N/2)! | N!/((N/2)! 2^(N/2))
6 720 | 120 | 15
8 40320 | 1680 | 105
10 3628800 | 30240 | 945
46 5.5x10^57 | 2.1x10^35 | 2x10^28