从数组的所有可能大小为'k'的子集中取最大元素的和

Question

我有一个非常大的列表，里面大约有10,000个元素，每个元素都是一个可以达到50亿的整数。我想要找到每个可能的大小为'k'（由用户指定）的子集中的最大元素的总和。现在我想到的唯一解决办法就是生成每一个子集（用itertools库），然后找出它的最大元素。但是这样做会花费非常多的时间！有没有什么更好的方法可以用Python来解决这个问题呢？

Answer 1

先别急着用Python，先用数学来解决问题。这是一个组合问题：假设你有一个包含n个数字的数组S（n很大），你想生成所有大小为k的子集，并计算这些子集中最大元素的总和。

假设这些数字都是不同的（即使不是也没关系），你可以准确计算每个数字在子集中出现的次数，然后就可以继续计算，而不需要实际构建子集。如果你把这个问题放到math.stackexchange.com上，他们会很快帮你解决的。这里是大致的思路，但没有那么复杂的数学符号：

先把你的数组按从小到大的顺序排序，S_1是最小的数字，S_2是下一个最小的，以此类推。（注意：索引从1开始）。

1. S_n，也就是最大的元素，显然是它所在的任何子集中的最大元素，而这样的子集有(n-1 choose k-1)个。

2. 对于那些不包含S_n的子集，有(n-2 choose k-1)个子集包含S_{n-1}，在这些子集中它是最大的元素。

3. 继续这样推算，直到你到达S_k，也就是第k个最小的数字（从最小的开始算），它将是恰好一个子集的最大值：(k-1 choose k-1) = 1。更小的数字（S_1到S_{k-1}）永远不可能是最大值：每个包含k个元素的集合中都会有更大的数字。

4. 把上面提到的(n-k+1个项)相加，这就是你的答案：

   S_n*(n-1 choose k-1) + S_{n-1}*(n-2 choose k-1) + ... + S_k*(k-1 choose k-1)
   

   把这些项从小到大写出来，这就是简单的总和

   Sum(i=k..n) S_i * (i-1 choose k-1)    
   

如果我们在math.stackexchange上，你会看到更正式的数学符号，但你大概明白了这个思路。