在Python中按其元素的总和对组合进行排序

Question

我有一个巨大的Python整数列表(1000000+元素),但为了简单起见,我将用一个例子来说明我需要的东西.我们假设我有这个清单:

A = [1,2,3,4,100]

现在我想得到该列表的所有组合(大小3),所以我使用itertools.

combinations = itertools.combinations(A,3)

但我的问题是,这将按字典顺序返回组合:

(1,2,3)
(1,2,4)
(1,2,100)
(1,3,4)

等等.

我想得到按其元素总和排序的组合.那将是:

(1,2,3)总和6,(1,2,4)和7,(1,3,4)和8,

等等.

我怎样才能做到这一点？

Answer 1

有序组合太大，无法容纳在内存中

1,000,000 个事物一次取 3 个的组合数为 166,666,166,667,000,000。它太大，无法放入内存，太大，无法排序，甚至太大，无法在合理的时间内循环。

有关延迟生成这些组合的方法，请参阅Donald Knuth 的组合算法分册中的“生成所有组合”。

适合记忆的有序组合

只要组合的数量合理，最直接的方法就是直接按组合的总和排序：

>>> import itertools
>>> import pprint

>>> A = [1, 2, 3, 4, 100]
>>> combinations = sorted(itertools.combinations(A, 3), key=sum)
>>> pprint.pprint(combinations)
[(1, 2, 3),
 (1, 2, 4),
 (1, 3, 4),
 (2, 3, 4),
 (1, 2, 100),
 (1, 3, 100),
 (1, 4, 100),
 (2, 3, 100),
 (2, 4, 100),
 (3, 4, 100)]

该技术使用sum()作为Sorted()的关键函数。

连接两个世界

当nCr大于实际可以枚举的值时，通过从列表A中删除较大的元素直到总和足够大以包含这些值来减少问题是有意义的。