458,183 Members | 1,382 Online Need help? Post your question and get tips & solutions from a community of 458,183 IT Pros & Developers. It's quick & easy.

# Combination problem - fast algorithm

 P: n/a I have this problem. I'm trying to get all the valid combination C(N,K) that pass one condition. For example C(5,3) can use in any combination this numbers {1,2,3,4,5} But let's say that I have the limitations that these pair of numbers cannot be part of the same combination {2,3} and {4,5} So the right soolution are only : {1,2,4} {1,2,5} {1,3,4} {1,3,5} My sollution for a test of C(20,13) with 7 pairs of numbers took me about 25s, but it's too much for my needs. Does anyone has a better algorithm ? Apr 28 '06 #1
6 Replies

 P: n/a aka_eu opined: I have this problem. I'm trying to get all the valid combination C(N,K) that pass one condition. For example C(5,3) can use in any combination this numbers {1,2,3,4,5} But let's say that I have the limitations that these pair of numbers cannot be part of the same combination {2,3} and {4,5} So the right soolution are only : {1,2,4} {1,2,5} {1,3,4} {1,3,5} My sollution for a test of C(20,13) with 7 pairs of numbers took me about 25s, but it's too much for my needs. Does anyone has a better algorithm ? Most certainly, or at least a faster machine. However, it's impossible to say with absolute certainty since you didn't show us yours. Or do you expect us to guess? In any case, general algorithms are the stuff of comp.programming. Generally, optimisations are not discussed in comp.lang.c, either, but if you show us some code, someone may bite. -- If God had intended Man to Watch TV, He would have given him Rabbit Ears. Apr 28 '06 #2

 P: n/a My algorithm is the most simply one for(p1=1;p1<=5;p1++) for(p2=p1+1;p2<=5;p2++) for(p3=p2+1;p3<=5;p3++) if (CondtionIsTrue) printf(p1,p2,p3); Apr 28 '06 #3

 P: n/a aka_eu wrote On 04/28/06 09:49,: I have this problem. I'm trying to get all the valid combination C(N,K) that pass one condition. For example C(5,3) can use in any combination this numbers {1,2,3,4,5} But let's say that I have the limitations that these pair of numbers cannot be part of the same combination {2,3} and {4,5} So the right soolution are only : {1,2,4} {1,2,5} {1,3,4} {1,3,5} My sollution for a test of C(20,13) with 7 pairs of numbers took me about 25s, but it's too much for my needs. Does anyone has a better algorithm ? No. The word "better" implies a comparison between two things, in this case two algorithms, and since you have not revealed your algorithm there is no way to compare another one to it. Even after you've disclosed your code, there's no way to be 100% some alternative would be faster other than to write it up and try it. The language itself has no notion of the speed of any construct or combination of constructs, and the actual speed of some piece of code will vary from one implementation to another, sometimes widely. That said, your current code gets through only 3100 combinations per second, a rate that might have been pretty good fifty years ago but looks astonishingly slow today. There's an excellent chance that your super-secret algorithm is doing something silly, and that someone will be able to suggest significant improvements if you take the covers off. -- Er*********@sun.com Apr 28 '06 #4

 P: n/a On Fri, 28 Apr 2006 06:49:54 -0700, aka_eu wrote: I have this problem. I'm trying to get all the valid combination C(N,K) that pass one condition. For example C(5,3) can use in any combination this numbers {1,2,3,4,5} But let's say that I have the limitations that these pair of numbers cannot be part of the same combination {2,3} and {4,5} So the right soolution are only : {1,2,4} {1,2,5} {1,3,4} {1,3,5} My sollution for a test of C(20,13) with 7 pairs of numbers took me about 25s, but it's too much for my needs. Does anyone has a better algorithm ? As noted elsewhere, this is off topic. In the case that you have k pairs (and no number occurs in more than one pair) and you want to split the numbers up into one subset of k numbers and the rest -- as both your examples -- the k element subset must contain exactly one number from each pair (otherwise we would have a pair in the same subset). So there are 2^k such splittings; you could get them all by running through all k bit numbers, and for each such number x, and i = 0..k-1, choose the the first element of the i'th pair to be in the k-element subset if the i'th bit of x is clear, otherwise choose the second element. Duncan Apr 28 '06 #5

 P: n/a aka_eu wrote: My algorithm is the most simply one for(p1=1;p1<=5;p1++) for(p2=p1+1;p2<=5;p2++) for(p3=p2+1;p3<=5;p3++) if (CondtionIsTrue) printf(p1,p2,p3); Please review the information below. Brian -- Please quote enough of the previous message for context. To do so from Google, click "show options" and use the Reply shown in the expanded header. Apr 28 '06 #6

 P: n/a "aka_eu" wrote in message news:11**********************@e56g2000cwe.googlegr oups.com... I have this problem. I'm trying to get all the valid combination C(N,K) that pass one condition. For example C(5,3) can use in any combination this numbers {1,2,3,4,5} But let's say that I have the limitations that these pair of numbers cannot be part of the same combination {2,3} and {4,5} So the right soolution are only : {1,2,4} {1,2,5} {1,3,4} {1,3,5} My sollution for a test of C(20,13) with 7 pairs of numbers took me about 25s, but it's too much for my needs. Does anyone has a better algorithm ? Maybe. (I'll post some code below.) I pulled out my probability and statistics textbook from years ago. If there was a quick answer in there, I didn't find it. The first problem I see is how to quickly determine if {2,3}or {4,5} is in the generated set: {1,2,3} {1,2,4} {1,2,5} {1,3,4} {1,3,5} {1,4,5} {2,3,4} {2,3,5} {2,4,5} {3,4,5} {2,3} could be the 2nd & 3rd values or the 1st & 2nd. This gets worse for C(20,13). {14,15} could be in six(?) different positions. This would suggest fixing the positions, i.e., 2 always in the 2nd position: {1,2,3,0,0} {1,2,0,4,0} {1,2,0,0,5} {1,0,3,4,0} {1,0,3,0,5} {1,0,0,4,5} {0,2,3,4,0} {0,2,3,5,0} {0,2,0,4,5} {0,0,3,4,5} Unfortunately, this would also cause unnecessary additional looping to search for valid non-zero values, but it has the advantage of easily determining if {2,3} or {4,5} is in the set since the positions are fixed. So, can we get the benefits of this without the disadvantages? Yes. We can use one array with fixed positions as indicators, and another array for the set of values: {1,2,3} {1,1,1,0,0} {1,2,4} {1,1,0,1,0} {1,2,5} {1,1,0,0,1} {1,3,4} {1,0,1,1,0} {1,3,5} {1,0,1,0,1} {1,4,5} {1,0,0,1,1} {2,3,4} {0,1,1,1,0} {2,3,5} {0,1,1,0,1} {2,4,5} {0,1,0,1,1} {3,4,5} {0,0,1,1,1} Now we have one array with the valid values and a quick way to exclude unwanted sets. This code has an #if directive that allows you to see the entire computation or just the valid sets (change from '#if 0' to '#if 1'). #include #include #include #define N 5 #define K 3 unsigned long val[K]; unsigned char ind[N+1]; /* "boolean" */ void cnk(void) { unsigned long p1,p2,p3; unsigned long i; unsigned char exclude; memset(ind,0,N); for(p1=1;p1<=N;p1++) { val=p1; ind[p1]=1; for(p2=p1+1;p2<=N;p2++) { val=p2; ind[p2]=1; for(p3=p2+1;p3<=N;p3++) { exclude=0; val=p3; ind[p3]=1; #if 0 /* change 0 to 1 for full complete info */ for(i=0;i

### This discussion thread is closed

Replies have been disabled for this discussion. 