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 » 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?

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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

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 » 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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

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.

Post Reply

Return to “C++”