3

我有一个非常大的列表，包含大约 10,000 个元素，每个元素都是一个 50 亿大的整数。我想从最大大小为 10,000 个元素的数组的每个可能的大小“k”子集（由用户给出）中找到最大元素的总和。我想到的唯一解决方案是生成每个子集（使用 itertools）并找到它的最大元素。但这将花费大量时间！解决这个问题的pythonic方法是什么？

4

1 回答 1

6

不要用python，先用数学。S这是一个组合问题：如果您有一个包含n 个数字（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-th数（从最小的数），这将是恰好一个子集的最大值：(k-1 choose k-1) = 1。较小的数字 ( S_1to S_{k-1}) 永远不会是最大的：每组k元素都将包含更大的东西。

  4. 总结以上内容(n-k+1 terms)，你的答案就是：

    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 上，你会得到正确的数学符号，但你明白了。

于 2013-02-03T18:34:09.903 回答