如何从M个物品中每次取出N个？

Question

如何从M个物品中每次取出N个？

python

3

我有一个包含46个项目的列表，每个项目都有一个相关联的编号。我想将这些项目配对成23组。我想对每个组执行一个函数。如何生成这样的一组？

我可以使用itertools中的combinations函数生成所有的2元组，但我不知道如何生成所有的23个项目的配对。请问该如何实现或是否有示例代码可供参考？

- user1625344

1

please show example input - jamylak

这些对中顺序是否重要？ - Vaughn Cato

你是说你想要所有可能的23个项目集，其中每个项目都是来自原始46个项目集中的一对项目吗？原始集合中有1035个成对项目。这意味着那些成对项目的23个项目集的数量为1035选择23，大约是50 quattuordecillion - 也就是后面跟着46个零的5。你不太可能能够对这个巨大的组合数做任何有用的事情。 - BrenBarn

2个回答

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

如果你想生成所有这样的配对，我会做类似于以下的事情（这就是我所谓的Case 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)

考虑到这个“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 ²⁸）。

编辑：人们批评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

注意，我的算法将遍历所有排列，因此对于Case 3（由于排序）实际上运行速度会比Case 1慢，尽管Case 3的更好算法可能会快得多。然而，即使Case 3在渐近符号中是阶乘级别的时间复杂度，完全无法解决N〜46的问题，我的答案仍然是最优的。当然，如果您必须处理接近可行性极限（N〜16）的问题大小的Case 3（例如，需要生成518918400.0个配对），则通过迭代所有N！排列，排序并且丢弃重复项的解决方案是次优的。

- dr jimbob

4

请注意，需要进行42次迭代。以每秒一万亿次的速度计算，这将需要4450万亿亿年才能完成。如果有人很着急的话，请记住这个时间。 - Cairnarvon

好的，作为楼主，我意识到我需要重新制定如何找到实际解决方案的计划。感谢您指出这个问题的重要性。 - user1625344

@Cairnarvon - 是的，它具有N!的运行时间。但是正如我的编辑所示，对于原始问题的任何合理解释，期望解决方案的数量随着O(N!)增长，并且解决N=46是完全不可行的。至少这个解决方案适用于非常小的值；与gnibblers不同，它没有回答问题。 - dr jimbob

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John La Rooy · Accepted Answer

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