1

K個の値とn個のアイテムのすべての組み合わせを見つけるアルゴリズムを探しています。

例：

K値は[R、B]であり、Nは2であるため、{RR、RB、BR、BB} 2 * 2=4つの方法が得られます。

K値は[R、B]であり、Nは3であるため、{RRR、RRB、RBB、RBR、BRR、BRB、BBR、BBB} 2 * 2 * 2=8つの方法が得られます。

K個のアイテムをN個のスロットに配置できるすべての可能な方法を見つけるために、一般的なアルゴリズムを見つける必要があります。（繰り返し可能）

別の例は次のとおりです。

Kの値は[R、G、B]で、Nは5なので、3 ^ 5=81の組み合わせを見つける必要があります。

4

2 に答える 2

2

この問題は、再帰的な解決策に非常に適しています。

一般的な場合の解は、の解を取り、N - 1次にセットの各要素を結果に順番に追加することによって明確に形成されます。擬似コードの場合：

f(options, 0) = []
f(options, n) = options foreach o => o ++ f(options, n-1)

これはJavaで再帰的に実装できますが、n;の値が適度に大きい場合にスタックオーバーフローエラーが発生します。また、JITコンパイラは再帰的アルゴリズムの最適化にあまり効果がないため、パフォーマンスが低下する可能性があります。

ただし、再帰的アルゴリズムは常に同等のループに変換できます。この場合、次のようになります。

List<String> results = new ArrayList<String>();
results.add(""); // Seed it for the base case n=0
for (int i = 0; i < n; i ++) {
    List<String> previousResults = results;
    results = new ArrayList<String>();
    for (String s : options) {
       for (String base : previousResults) {
           results.add(s + base);
       }
    }
}
return results;

これは再帰的な方法と同様に機能します（各反復で現在の進行状況（つまりの結果n-1）を「保存」しpreviousResults、次にオプションを順番に繰り返して、前のオプションの前に追加した結果を取得します結果。

自動再帰から反復へのアルゴリズムを再帰的ソリューションに渡すことの効果を確認し、読みやすさとパフォーマンスの両方をこの手動で作成したものと比較するのは興味深いことです。これは読者の練習問題として残されています。

于 2012-07-06T11:09:47.667 に答える
1

ベース樽でNビットのカウンターを使用します：k = 3、n = 5

(0,0,0,0,0)
(0,0,0,0,1),
....
(2,2,2,2,2)

このようなカウンターの実装は簡単です。サイズn+1の配列を維持し、最初はすべての要素をゼロに設定し、毎回最新の要素を増やし、k-1を超える場合は、次の隣接要素を増やします（隣接要素がk-1を超えるまで） ）。n + 1要素が1に設定されると、アクションは終了します。

試してもできなかった場合は、コメントで伝えてください。

于 2012-07-06T11:20:27.963 に答える