この問題は、再帰的な解決策に非常に適しています。
一般的な場合の解は、の解を取り、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
、次にオプションを順番に繰り返して、前のオプションの前に追加した結果を取得します結果。
自動再帰から反復へのアルゴリズムを再帰的ソリューションに渡すことの効果を確認し、読みやすさとパフォーマンスの両方をこの手動で作成したものと比較するのは興味深いことです。これは読者の練習問題として残されています。