Better algorithm for this ? (generating combinations)

The problem is to generate all possible unique selections of n numbers from a given set of size > n.

I've pretty much done it by brute force, as the number of final results should be same whichever way I choose. If a better way is not possible, I'd like suggestions about simple optimizations.

Code:

`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;

}

I noticed that having the return container a deque makes this much faster than if a vector or list is used. Why ?

Also, is it worth the trouble trying to do it iteratively?

Finally, can anyone help me determining the complexity of this function ?

(I think it is something near (log base n U.size() )^ n) but I'm probably very very wrong about that.)

Btw, here is a main you can use to test it.

Code:

`int main(int argc,char** argv)`

{

std::set<int> input;

for(int i=0;i<atoi(argv[1]);i++)

input.insert(i);

auto foo = find_combinations(input,atoi(argv[2]));

// for(auto x:foo) //displaying results

// {

// for(auto y:x)

// std::cout<<y<<'\t';

// std::cout<<std::endl;

// }

}