複雑さを軽減するために、サイズnのサブセットを1つずつ生成するには？

Question

void AlgoMMPCbar::subs(const std::vector<unsigned int>& org, const std::vector<unsigned int>& pre, size_t k, size_t n, SubSets& c){ 
    if (n <= 1) { 
    for(size_t i = k; i < org.size(); i++){ 
     std::vector<unsigned int> v(pre);// instead of printing... 
     v.push_back(org.at(i)); 
     c.push_back(v); 
    } 
} else { 
    size_t n1 = n - 1; 
    for(size_t i = k; i != org.size() - n1; i++){ // 
     std::vector<unsigned int> s(pre); 
     s.push_back(org.at(i)); 
     subs(org,s,i+1,n1,c); 
    } 
} 
} 
void AlgoMMPCbar::computeSubSets(const std::vector<unsigned int>& org, size_t& n, SubSets& c){ 
c.clear(); // clear previous data 

std::vector<unsigned int> pre; 
pre.reserve(n+1); // for performance 
    if (n==0) 
     c.push_back(pre); 
else 
     subs(org,pre,0, n, c); 
} 

上記のコードは、さらなるテスト/処理のためにサイズnのサブセットを生成するために使用されました。しかし、これらの生成されたサブセットをすべてテストする必要はありません（最悪の場合は、すべてをチェックします）。プログラムの主要な時間はサブセットの生成です。今私は上記の機能を1つずつサブセットを生成するように変換したい（一度にすべてではないので、いつでもサブセットの生成を止めることができます）。

計算時間を節約するために、上記の機能をsubset.next（）のような関数に変換する専門知識を共有してください。

ありがとうございます。

Answer 1

あなたは

によって次のサブセットに行くことが最も小さい jな

j == n-1 || ind[j] + 1 < ind[j+1] 

ことがわかりすなわち

ind[0] < ind[1] < ... < ind[n-1] 

、indが昇順にサブセット内の要素のインデックスを維持して言います

ind[j]++ 
ind[0] = 0; ind[1] = 1; ... ind[j-1] = j-1 

新しいind配列はまだソートされています。

ind[] = [0, 1, ..., n-1] 

から始めると、上記の手順を繰り返してすべての部分集合を生成することが簡単にわかります。リニア検索を行うのではなく、上記の値jを「維持」するためにいくつかのトリックを使用すると、高速なコードを作成できます。

Answer 2

subs関数は、boolを返すことができます。 ifのn<=1支店では、それぞれのチェックを実行できます。現在のサブセットが一致する場合は、保存してtrueを返します。他のブランチでは、コールをif (subs(..)) return true;のように置き換えます。最後にreturn falseを追加します。 複数のサブセットが必要になる可能性があり、そこにどれだけ適しているかを正確に把握していない場合は、何をすべきか分かりません。

Answer 3

私はいくつかのソート状態ベクトルを作成し、それを辞書的にステップスルーします。したがって、M要素のセットがあり、サイズがnのサブセットが必要な場合は、選択したインデックスに対応するベクトルnの整数があります。次に、次のサブセットを取得するアルゴリズムnext_subset(std::vector<bool> &)を作成します。 5の大きさ-3のサブセットのための例：

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

私は（あなたがパターンを見つけることができると確信している最後の場所をインクリメント;などなど、それは終わりだ場合、バックに移動し、最大2つの最後の場所をインクリメント）。

さらに効率的にしたい場合は、コンテナがランダムアクセスでない場合は、元のコンテナまたは整数とイテレータのペアにイテレータを格納できます。