cod*_*res 3 python algorithm subset
我有一个非常大的列表,包含大约10,000个元素,每个元素是一个大到50亿的整数.我想从最大大小为10,000个元素的数组的每个可能的大小'k'(由用户给出)子集中找到最大元素的总和.我想到的唯一解决方案是生成每个子集(使用itertools)并找到其最大元素.但这需要花费大量时间!解决这个问题的pythonic方法是什么？
不要使用python,首先使用数学.这是一个组合问题:如果你有一个数组S的ñ号(ñ大),并生成大小的所有可能的子集ķ,你要计算的子集的最大元素的总和.
假设这些数字都是不同的(尽管它们也是有效的),你可以准确计算每个数字在子集中出现的频率,并从那里开始,而不必实际构建一个子集.你应该把它拿走math.stackexchange.com,他们已经把你整理好了.在这里,但没有很好的数学符号:
按递增顺序对数组进行排序,让它S_1成为最小(第一个)数字,S_2下一个最小数字,
依此类推.(注意:从1开始索引).
S_n,最大的元素,显然是它所属的任何子集的最大元素,并且确实存在(n-1 choose k-1)这样的子集.
在不包含S_n的(n-2 choose k-1)
子集中,存在包含的子集,S_{n-1}其中它是最大的元素.
继续下去,直到你下来到S_k的k-th最小的数字(从最小计数),这将是最大的只有一个子集:(k-1 choose k-1) = 1.较小的数字(S_1to S_{k-1})永远不会是最大的:每组k元素都会包含更大的元素.
总结以上(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上你会得到正确的数学符号,但你明白了.