3

約 10,000 の要素で構成される非常に大きなリストがあり、各要素は 50 億の整数です。最大サイズが 10,000 要素である配列のサイズ 'k' (ユーザーが指定) のすべての可能なサブセットから最大要素の合計を見つけたいと思います。私の頭に浮かぶ唯一の解決策は、(itertools を使用して) 各サブセットを生成し、その最大要素を見つけることです。しかし、これには非常に時間がかかります。これを解決するためのpythonicな方法は何でしょうか?

4

1 に答える 1

6

Python を使用しないでください。最初に数学を使用してください。これは組み合わせの問題です: n 個の数値 ( n 個の大規模) の配列があり、Sサイズ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. 最小の数 (最小から数えて) になるまでこれを続けます。これは、ちょうど 1 つのサブセットの最大にS_kなります。より小さい数 ( to ) が最大になることはありません。要素のすべてのセットには、より大きなものが含まれます。k-th(k-1 choose k-1) = 1S_1S_{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 に答える