ほとんどの場合、列挙の問題は再帰列挙によって解決されます。残念ながら、一般的なアプローチはありません。多くの場合、反復方法はタスク自体に大きく依存します。
ただし、さまざまな組み合わせオブジェクトの列挙方法の間には、いくつかの類似点があることに気づくことができます。したがって、説明のための例として、n から k までのすべての組み合わせを生成するコードを考えてみましょう。
int n、k;
// プレフィックスの組み合わせをサポートする配列。
///
// この場合の接頭辞は、組み合わせでいくつかのオブジェクトを選択したことを意味します。
///
// その後、正しい組み合わせで完成します。
// あるいは、そのようなプレフィックスが正しく完成できないことがわかった場合、再帰によってブランチが切断されます。
vector arr;
// 再帰的反復関数自体
///
// pos - 組み合わせたオブジェクトの番号。現時点で決定します (0 から k - 1)
///
// prev - 前のステップで取得したオブジェクトの値
///
// 組み合わせでは、オブジェクトの順序は重要ではありません ([1, 2] と [2, 1] は同じで類似しているとみなされます)。
// したがって、オブジェクト値が昇順になっているセットのみを生成したいと考えています。
///
// これは、[1, 2] や [2, 1] などの同じオプションが 1 回だけ繰り返されるようにするために必要です
// (この場合、[1, 2] のみを考慮しますが、[2, 1] は順序セットではないため考慮しません)。
///
// そのため、反復回数を減らすために prev 変数を保持します。
void rec(int pos, int prev) {
// 選択された要素の数が k に等しい場合、すでにすべての要素が選択されています
// なぜならそれらの番号は 0 から k - 1 までです
if (pos == k) {
// 条件が満たされる場合、正しい組み合わせが arr 配列内にあります
// そして、何らかの方法でそれを処理できます (この場合は、単にコンソールに出力するだけです)
for (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
戻る; // 再帰ブランチを切断します。すでに組み合わせを取得しているため、これ以上続ける必要はありません
}
// ここで、残りの要素から正しい組み合わせを取得できるかどうかを確認します
// 十分な要素が残っていない場合は、この再帰分岐を切り取ります
if (k - pos > n - prev - 1)
戻る;
// インデックス pos の位置に配置したオブジェクトを反復処理します。
// しかし理由は順序付きセットが必要な場合、可能な最小値は prev + 1 です。
for (int i = prev + 1; i < n; i++) {
arr.push_back(i); // グローバル配列に要素を追加します。今、私たちは彼を選んだようです
rec(pos + 1, i); // 再帰的に実行して以下の項目を設定します
arr.pop_back(); // 再帰から戻った後、現在選択されている要素は関連性がなくなります。
// なぜなら再帰の内部では、このような接頭辞を持つすべてのオプションを調べました。
// したがって、この要素は削除する必要があります
}
}
int main()
{
シン>> n>>; k;
// 最初に要素を 0 番目の位置に設定します
// 要素 -1 が以前に選択されていると想定するため、反復は最初に null オブジェクトから開始されます。
rec(0, -1);
0 を返します。
}
同じコードですが、コメントはありません:
int n、k;
vector arr;
void rec(int pos, int prev) {
if (pos == k) {
for (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
戻る;
}
if (k - pos > n - prev - 1)
戻る;
for (int i = prev + 1; i < n; i++) {
arr.push_back(i);
rec(pos + 1, i);
arr.pop_back();
}
}
int main() {
シン>> n>>; k;
rec(0, -1);
0 を返します。
}
再帰的反復では、再帰カットに常に特別な注意を払う必要があります。実際には、プログラムを大幅に高速化できます。
|