組み合わせ論と列挙についてたくさんの質問があることは承知していますが、私が探しているものに特に関連するものは何も見つかりませんでした。私が何かを見逃した場合は、それを指摘してください。質問を閉じることができます.
したがって、N 個の要素のセットがあり、Sum(k1,...,kx) <= N である x 個の正の整数 k1,...,kx があると仮定します。選択できるすべての方法を列挙したいと思います (置換なし) N の元のセットから、指定されたサイズの x サブセット。
私はそれを正しく表現したことを願っています。そうでない場合に備えて、簡単な例を示します。
N = 4、x = 2、k1 = 2、k2 = 1。
列挙する必要があります
- {1, 2} {3}
- {1, 2} {4}
- {1, 3} {2}
- {1, 3} {4}
- {1, 4} {2}
- {1, 4} {3}
- {2, 3} {1}
- {2, 3} {4}
- {2, 4} {1}
- {2, 4} {3}
- {3, 4} {1}
- {3, 4} {2}
一般的なケースでは、合計数は次のようになります。
C(N, k1) * C(N - k1, k2) * ... * C(N - Sum(k1,...,kn-1), kn)。
私の最初の推測では、これはスタックを使用してかなり簡単に実行できるということです。各スタック レベル i で、標準的な組み合わせの列挙を使用してサブセット ki が生成されます。各レベルで選択された要素をソース セットから削除するか、元のセットから列挙して、要素が以前に含まれていた場合をスキップします。 .
私の質問は、より高速でエレガントなソリューションはありますか?