3

我有一个包含 46 个项目的列表。每个都有一个与之关联的数字。我想将这些物品配对成一组 23 对。我想评估每个集合的函数。如何生成这样的集合？

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

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

4

2 回答 2

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]

编辑：

对于对的幂集，我们首先以相同的方式创建对。对于 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)
于 2013-05-28T03:54:51.027 回答
0

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

>>> 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）：

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

假设这将区分对中的顺序（例如，（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，将为 25373791335626257947657609375 ~ 2.5 x 10 28）。

编辑：人们批评了 O(N!)，但所需的解决方案随着 O(N!) 的增长而增长

该问题要求将 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

请注意，我的算法将遍历所有排列，因此对于案例 3（由于排序）实际上会比案例 1 运行得更慢，即使案例 3 的更好算法可能会快得多。但是，我的答案在渐近符号中仍然是最佳的，因为即使案例 3 在其渐近运行时间中也是阶乘，并且完全无法求解 N~46。如果您必须在案例 3 的可行性极限 (N~16) 下做一个问题大小（例如，需要生成 518918400.0 对），那么这种迭代所有 N! 排列、排序和丢弃重复项是次优的。

于 2013-05-28T03:59:34.423 回答