Combination problem - fast algorithm

[aka_eu]

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 ?

 

[Vladimir Oka]

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.

 

[aka_eu]

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);

 

[Eric Sosman]

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.

 

[Duncan Muirhead]

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

 

[Default User]

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

 

[Rod Pemberton]

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 <stdio.h>
#include <stdlib.h>
#include <string.h>

#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[0]=p1;
ind[p1]=1;
for(p2=p1+1;p2<=N;p2++)
{
val[1]=p2;
ind[p2]=1;
for(p3=p2+1;p3<=N;p3++)
{
exclude=0;
val[2]=p3;
ind[p3]=1;
#if 0
/* change 0 to 1 for full complete info */
for(i=0;i<K;i++)
printf("%ld ",val);
printf(" ");
for(i=0;i<N;i++)
printf("%d ",ind);
if(ind[2]&&ind[3])
printf("*");
if(ind[4]&&ind[5])
printf("*");
printf("\n");
#else
/* only print reduced sets */
if(ind[2]&&ind[3]) /* eliminate {2,3} */
exclude=1;
if(ind[4]&&ind[5]) /* eliminate {4,5} */
exclude=1;
if(!exclude)
{
for(i=0;i<K;i++)
printf("%ld ",val);
printf("\n");
}
#endif
ind[p3]=0; /* clear indicator */
}
ind[p2]=0; /* clear indicator */
}
ind[p1]=0; /* clear indicator */
}
}

int main(void)
{
cnk();

return(EXIT_SUCCESS);
}


HTH,

Rod Pemberton