S - アルゴリズム、ランダムと等しい合計で範囲からK個の一意の乱数を選択する

範囲があります

R = {0, ..., N}

そして私は得るのが好き K 合計が等しい要素 S、ただし、要素はランダムに選択する必要があります。

したがって、簡単なブルートフォースメソッドは、以下を含むすべての要素の組み合わせを決定することです。 K 結果として生じる数字 S ランダムに組み合わせの1つを選択します。

私は再帰的な解決策を考えていますここで、乱数が選択され、問題は（S-K0）に等しい合計で（K-1）の乱数を見つけるために減少しますが、これは解をもたらす必要はありません。

より良いアプローチがありますか？

サンプルは次のようになります。

R = {0,1,2,3,4,5}, S = 5, K = 2
Solutions: randomly pick one of {{1,4};{2,3};{0.5}}

回答：

回答№1は1

一般に、Kが大きく（そしてNも）、Sが少なすぎない場合、2つの多くの組み合わせがあるため、予測できません。

ブルートフォース：すべての組み合わせを試してください。解決策が存在する場合は必ず見つかりますが、たとえば1 Mdまたはそれ以上の数がある場合は、すべてをリストすることはほとんど不可能です。

あなたのアルゴリズム：

ランダムに選択するには、アルゴリズムは大丈夫です。1つの番号をランダムに取得し、次に別の番号を取得します...

しかし、あなたは仮定をします：あなたが選ぶ数字で解決策が存在する：あなたは知らない。

だから何 ？統計的に多くの解決策が存在する場合、そのように見つけることができます。 おそらく、または おそらくない.

いくつかのトレイル：

1 S / Kを使用

すべての数値がS / K未満の場合、不可能です。

すべての数値がS / Kより大きい場合、不可能です。

したがって、数字が<S / Kであり、その他が> S / Kであると仮定しましょう。

2数値<Sのみを保持します。Sが小さい場合は非常に興味深いです。

3アイデア：Sが大きく、数が少ない場合、多くの組み合わせが存在する可能性があります。

アルゴリズムのアイデア

1ランダムに1つの数N1を取る

N1 <S / Kの場合は2、別のN2> S / Kを取得

3 N1 + N2を計算します：<2.S / Kの場合は別のN3> S / Kを、そうでない場合は

4各ステップで繰り返します：sum <n S / Kの場合、別のものを取得> S / K、そうでない場合

5 S / Kを（S-sum N1、N2、...）/（K-n）に置き換えることで、精度を向上させることができます

1つのステップで番号が見つからない場合は、バックトラックします

それが役に立てば幸い

---

回答№2の場合は1

まず、ディリクレ分布（https://en.wikipedia.org/wiki/Dirichlet_distribution）。これを使用すると、（0..1）分布乱数Xで均一にサンプリングできます。_私、そのような合計_私バツ_私 = 1。

ために S <= N、それを超えるサンプリングは簡単にわかります S 無駄であり、完全に拒否されるべきです。

だから、受け入れ/拒否、ラインに沿った何かと組み合わせる

• 間隔[0 ... 1]を分割する S （または S+1 0が許可されている場合）ビンが等しい。
• サンプル K ディリクレ分布からの数。
• サンプリングされた数値をビンインデックスにマッピングするので、サンプリングされた整数がサンプリングされます。 すべて以下 S 合計が等しい S.
• すべての整数が異なる場合、サンプリングを受け入れます。そうでない場合は、サンプリングを拒否し、ステップ2に進みます。

---