如何及时处理事情

Question

我有46个项目的清单。每个都有一个与之相关的数字。我想把这些东西一组23对。我想对每个集合求值一个函数。如何生成这样的集合？在

我可以使用itertools的combinations函数来生成所有的2-ples，但我不知道如何生成23对的所有集合。在

我该怎么做，或者是否有可以参考的示例代码？在

Answer 1

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

编辑：

对于对的powerset，我们从以相同的方式创建对开始。对于Python3，使用range代替xrange

^{pr2}$

这将是一个相当大的列表，您可能需要使用一个生成器表达式

for item in ({j for i, j in enumerate(S) if (1<<i)&k} for k in xrange(1<<len(S))):
    func(item)

Answer 2

首先，从列表中获取所有对的自然方法是：

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

如果你想生成所有这样的对，我会做一些类似的事情（下面我称之为案例1）：

^{pr2}$

如果这样的话，这将区分成对的顺序（例如，（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))

这不是一个有效的算法（下面我称之为案例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，其945将为25373791335626257947657609375~2.5x10²⁸）。在

编辑：人们批评O（N！），但所需的解决方案会增长为O（N！）在

这个问题要求将N个元素的列表（假设所有元素都是不同的）分成一组（N/2）对，不仅这样做一次，而且生成这些对的所有集。这个答案是唯一的答案。是的，它是指数级的慢，而且对于N=46完全不可行。所以我用N=10。在

对这个问题有三种合理的解释：

情况1:排序关系到元组中一对内的排序（例如，函数参数不是对称的），而且在一组对中对的顺序也很重要，那么我们将得到N！答案中数字配对的方法。这意味着在这种情况下，对（0,1）和（1,0）都被认为是不同的，对于N=4的情况，我们认为{(0,1), (2,3)}与{}不同。在

案例2:一对中的排序很重要，但在一组配对中，顺序是不相关的。这意味着我们将（0,1）和（1,0）视为不同的对，但是考虑（对于N=4的情况）集合{(0,1),(2,3)}与集合{}是相同的，不需要同时考虑这两个。在这种情况下，我们将有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

对于3的情况，排序算法比3的情况要慢得多。然而，我的答案在渐近表示法中仍然是最优的，因为偶数情况3在其渐近运行时间上是阶乘的，并且对于N~46完全不可行。如果你必须在案例3的可行性极限（N~16）下做一个问题大小（例如，需要生成518918400.0对），这种迭代所有N的解决方案是可行的！排列、排序和丢弃重复项是次优的。在