To generate a subset of size n one by one to reduce the complexity?

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); 
}

The above code used to generate subsets of size n for further test/processing. But i never need to test all these generated subsets (in worst case it will check them all). The main time consuming part of the program is the subset generation. Now i want to transform the above functionality to generate subsets one by one (not all at once, so, i can stop further subset generation any time).

Please share your expertise to transform the above functionality in a function like subset.next(), to save computational time.

Thanks in advance.

---

say ind maintains the indexes for elements in the subset in an increasing order, i.e.

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

find the smallest j such that

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

you may go to the next subset by

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

note that the new ind array is still sorted. You may easily show that starting with

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

you will generate all the subsets iterating through above procedure. you can have a fast code if you use some tricks for 'maintaining' the value of j in above rather than doing a linear search.

---

You could have your subs function return a bool. In the n<=1 branch of your if, you can run the respective checks, and if the current subset matches, you save it and you return true. In the other branch you replace the subs call by something like if (subs(..)) return true;. And you add a return false at the end. I have no idea what you should do if you potentially need more than one subset, and you don't know exactly how many suitable ones there are.

---

I would create some sort state vector and step through it lexicographically. So if you have a set of M elements and you want subsets of size n, you'd have a vector n integers corresponding to the selected indices. Then you make an algorithm next_subset(std::vector<bool> &) which gets the next subset. E.g for size-3 subsets of 5:

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

I'm sure you can spot the pattern (increment the last place; if it's at the end, move it back and increment the two last places up, etc etc).

If you want to be a bit more efficient, you can store iterators to your original container, or pairs of integers and iterators if the container isn't random-access.