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.
I noticed that having the return container a deque makes this much faster than if a vector or list is used. Why ?
std::deque<std::set<int>> find_combinations(const std::set<int>& U,unsigned int n)
if(n<1 || U.size()<n)//Nothing Happens Here !
else if(n==1) // The Universal input set is broken up and redistributed.
else // Recursion FTW, no comments !!
auto partial_result = find_combinations(temp,n-1);
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.
int main(int argc,char** argv)
auto foo = find_combinations(input,atoi(argv));
// for(auto x:foo) //displaying results
// for(auto y:x)