Combinations and Permutations

Write here if you have problems with your C++ source code

Moderator: Board moderators

Post Reply
bluebird
New poster
Posts: 12
Joined: Mon Oct 17, 2005 2:35 am
Location: Canada

Combinations and Permutations

Post by bluebird »

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
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

I think next_permutation is amortised constant time.

bluebird
New poster
Posts: 12
Joined: Mon Oct 17, 2005 2:35 am
Location: Canada

Post by bluebird »

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

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris »

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.

Post Reply

Return to “C++”