任意のデータの配列をN個のビンにグループ化する

Question

ランダムな値の任意のサイズの配列をグループにグループ化して、いずれかのグループ/ binの値の合計ができるだけ等しいようにしたい。

値[1, 2, 4, 5]とn = 2の場合、出力バケットは[sum(5+1), sum(4+2)]である必要があります。

私に起こるいくつかの可能性：

• 完全網羅幅が第1の和が等しくなるまで、グループ化、ソートされた配列の一端からハードコードされた停止条件と
• ランダムプロセス
• スタートを検索世界平均し、nが

に到達するまで、次のグループに移動すると、最適解（の和のように思えますビンの内容は入力配列が与えられているので可能な限り等しい）はおそらく重要ではない。だから、私は最後の選択肢に向かって傾いていますが、もっと洗練されたソリューションが欠けていると感じていますか？

Answer 1

これはNP困難な問題です。言い換えれば、すべての組み合わせを探索することなく最適解を見つけることは不可能であり、組み合わせの数はn^M（Mはあなたの配列のサイズ、nは豆の数）です。それはclusteringと非常によく似た問題です。これもまたNP困難です。

データセットが処理できるほど小さい場合は、ブルートフォースアルゴリズムが最適です（すべての組み合わせを調べます）。

しかし、データセットが大きい場合、最適解を得ることはできませんが、近似には多項式時間アルゴリズムが必要です。その場合、類似のものを使用することをお勧めしますK-Means ...

ステップ1.予想されるビンごとの合計を計算します。 を配列にすると、1ビンあたりの予想される合計はSumBin = SUM（A）/ n（ビン数に対する配列のすべての要素の合計）になります。

ステップ2. バッグ（これは単なる概念的なものなので、次のステップを理解している）と呼ぶコレクション（たとえば、別の配列）に配列のすべての要素を配置します。

ステップ3パーティションバッグ N に基（好ましくはランダムに、各要素は、いくつかのビンに終わるようI確率1/N 有します）。この時点で、ビンにはすべての要素があり、バッグは空です。

ステップ4.各ビンの合計を計算します。結果が最後の反復と同じ場合、出口。 （これは、期待値ステップのK-平均値）

ステップ5です。その合計がより大きくSumBinある場合は、各ビンについて私は、最初の要素よりも大きいSumBinを選び、バッグはに戻ってそれを置きます。その合計がSumBin未満の場合は、SumBin未満の最初の要素を選択し、The Bagに戻します。これは、勾配降下ステップ（別名最大化ステップ）がK-Meansです。

ステップ6. Goがこのアルゴリズムは単なる近似値である3

進むが、それは速く、収束する保証です。あなたの代わりにランダム要素を割り当てるのでは、ステップ3に戻ったときに、あなたが最初の反復の後、上記のような無作為化アルゴリズムについて懐疑的である場合

、あなたはHungarian algorithmを実行することにより、最適にそうすることができますが、私はないですより良い結果が得られることを確実にしてください。