Combinations and Permutations

bluebird · Post by **bluebird** » Thu Oct 27, 2005 2:42 am

I know in STL you can use the next_permutation algorithm to get permutations in linear time, but how do you get QUICK combinations in C++? e.g. how can I find all the different ways to choose 10 things out of 500 things in less than a few seconds, when the order doesn't matter?

I ask because I am having trouble doing this type of problems (e.g. Doublets and Crypt Kicker). Right now I am using a boolean array to get combinations. In the above example, I would have an array of 10 T and 490 F, and I would call next_permutation on the boolean array to get the next combination, but this seems to be too slow for most questions.

Has anyone found really clever ways to do this?

Cho · Post by **Cho** » Thu Oct 27, 2005 2:59 am

I think next_permutation is amortised constant time.

bluebird · Post by **bluebird** » Thu Oct 27, 2005 4:13 pm

I agree. But next_permutation should still be faster than using a recursive algorithm. Is there a faster way to do permutations/combinations?

Quantris · Post by **Quantris** » Wed Jan 25, 2006 9:02 am

I hope you realise that 500 choose 10 is enormous -- bigger than 10^20 -- no matter what method you use it's going to take a long time to enumerate (consider the printing time alone) them all.

next_permutation is quite fast for enumerating permutations. You can gain a little speed by implementing the same algorithm but without the STL overhead, but the gain is minor.