バックトラッキング/再帰を使用してすべての種類の置換と組み合わせを生成する

繰り返しが許されるかどうか、順序が問題であるかどうかに基づいて可能な4種類の順列または組合せがあります.
これらの4つをまとめ、以下の例で説明する.

再帰を使用して生成するには、再帰ツリーを作成します.

この木のすべての組み合わせは順列の最初のタイプ(n ^ r)です.繰り返しが許可されていない場合は、順序の問題は、ちょうど青いものをスキップします.ここでのポイントは、2歳のときにスキップされた2人の子供たちのような親のノードと同じように、ここでの項目をスキップしたことです.それで、これは繰り返しものの世話をします.今、順序が問題でないならば、我々カントは両方の1 2と2を取る.図では緑のものをスキップします.ここで注意してください.子供以下の要素をスキップするだけで、親要素から始まる要素を取ることができます.たとえば、1人の子供のために、我々は1から要素をとって始めます、2の子供のための1、1、2、11のように、我々は2、2、2のように2から要素を取って始めます、そして、3の子供たちのために3つの子供たちのために3、3のようなものから始めてください.
以下の観察に基づきます

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

void permComb(vector<int> data, int r, bool order, bool repeat, vector<int> out = {}, int i = 0, unordered_set<int> set = {})
{
    if (out.size() == r)
    {
        print(out);
        return;
    }

    for (int next = (order ? 0: i); next < data.size(); next++)
    {
        if (!repeat and set.find(data[next])!=set.end()) continue;
        set.insert(data[next]);     // to track repetitions
        out.push_back(data[next]);
        permComb(data, r, order, repeat, out, next, set);
        out.pop_back();
        set.erase(data[next]);
    }
    return;
}


int main()
{
    vector<int> data{ 1,2,3 };
    permComb(data, 3, true, false);
    return 0;
}

更新:

私は繰り返し配列を処理するために配列を使用することがより高速であることを実感しました.

あなたが4番目のタイプの組み合わせ(すべてのサブセットである)だけを望むならば、このコードは
順序なしで設定し、各選択肢で次の+ 1の代わりに次のパラメータを渡す.(この理由は、4番目の型の再帰木で見つけられる).また、別の再帰的ツリーアプローチを考慮することによって解決することもできます.これもビットマスキングで解決できる.

私はダイナミックプログラミングを学び始めました.この問題では、値と関連する重量の項目の束を与えられているまた、項目を入れて容量Wのナップサックを与えられた.そして、我々はアイテムを選ぶことによって達成される最大の利益を見つけて、それをナップサックに入れなければなりません.あなたがそれについて考えるならば、この問題は順序を要求しません、そして、タイプ4(または部分集合)タイプ問題である繰り返しはありません.これはバックトラッキングでも解決できます.

どのような問題があれば、別のタイプの順列を要求して、最初に再帰的なツリーを最初のタイプのように描き、解決策に合わないオプションをクロスして、コードスニペットに拡張しようとします.たとえば、私はLeetCodeでletter tile possibilities問題をしていました.これは、特定の文字がシーケンス内の一定の時間だけを使用することが要求されます.私は、私が説明したクロスチェック方法から得た考えを使ってそれを解決しました.

コメントであなたの考えを知らせてください.👋