Returning an std::deque<std::set<int>> looks expensive to me; I'd pass in the std::deque as a reference parameter and add results to it there. Also, it may be cheaper to pass along a single std::set<int> &U, where each recursive call removes items from U and then adds them back in as necessary. It depends on how expensive lookups and removals are (and other containers may be better in this regard, although you'd have to be careful to make the container stable -- add back to same position removed from). Maybe I'm too much of a Prolog programmer, but it makes way more sense to me to maintain data structures that are updated at each recursive call than making copies all the time. Also, this becomes much easier to convert to an iterative version if you like.
So here's how I would approach the problem. Sorry there aren't many comments in the code, ask me to elaborate if any of it is confusing.
Code:
#include <iostream>
#include <set>
#include <vector>
#include <deque>
std::deque<std::set<int>> find_combinations(const std::set<int>& U,unsigned int n)
{
std::deque<std::set<int>> result;
if(n<1 || U.size()<n)//Nothing Happens Here !
{}
else if(n==1) // The Universal input set is broken up and redistributed.
{
for(auto x:U)
result.push_back(std::set<int>({x}));
}
else // Recursion FTW, no comments !!
{
std::set<int> temp(U);
for(auto x:U)
{
temp.erase(x);
auto partial_result = find_combinations(temp,n-1);
for(auto& y:partial_result)
y.insert(x);
result.insert
(
std::begin(result),
std::begin(partial_result),
std::end(partial_result)
);
}
}
return result;
}
/** Generates combinations of @a data with @a n elements. Results will be added
to @a results, which should have @c data.size() choose @a n elements after
this function returns.
@a chosen and @a start indicate partial solutions, and should initially be
empty and zero, respectively.
*/
void find_combinations_dwk(std::deque<std::vector<int> > &results,
std::vector<int> &data, std::vector<int> &chosen,
unsigned start, unsigned n) {
if(n <= 0) {
results.push_front(chosen);
return;
}
for(std::vector<int>::size_type x = start; x < data.size(); x ++) {
int value = data[x];
data.erase(data.begin() + x);
chosen.push_back(value);
find_combinations_dwk(results, data, chosen, x, n - 1);
chosen.pop_back();
data.insert(data.begin() + x, value);
}
}
int main(int argc, char *argv[]) {
std::set<int> data;
std::vector<int> dataVector;
for(int x = 0; x < 20; x ++) {
data.insert(x);
dataVector.push_back(x);
}
if(argc == 1) {
auto size = find_combinations(data, 8).size();
std::cout << "find_combinations found: " << size << std::endl;
}
else {
std::deque<std::vector<int> > results;
std::vector<int> chosen;
find_combinations_dwk(results, dataVector, chosen, 0, 8);
std::cout << "find_combinations_dwk found: "
<< results.size() << std::endl;
}
return 0;
}
Timing results:
Code:
$ g++ --std=c++0x choose.cpp -o choose
$ time ./choose
find_combinations found: 125970
real 0m3.624s
user 0m3.576s
sys 0m0.044s
$ time ./choose dwk
find_combinations_dwk found: 125970
real 0m0.320s
user 0m0.300s
sys 0m0.020s
$
So it looks like my method is roughly an order of magnitude faster, at least for this input size! 
Of course it's not exactly a fair comparison, as I needed to use std::vector to avoid invalidated iterators while your method uses std::set, but I think you'll find that coding in this style can often be more efficient.
If you wanted to make my version iterative, it wouldn't be too hard. Just notice the only part that relies on recursion: really, the values of x. So all you'd need would be an std::stack of values of x, put the whole function into a loop and push and pop values of x as necessary. At least in theory.
Cheers, dwk.
[edit] Note I didn't actually check the output, but because the container has 20 choose 8 elements, I'm pretty sure it's correct. Or close enough. [/edit]
Originally Posted by phantomotap
