Combination problem - fast algorithm

Discussion in 'C Programming' started by aka_eu, Apr 28, 2006.

1. aka_euGuest

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 ?

aka_eu, Apr 28, 2006

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.

<http://clc-wiki.net/wiki/Introduction_to_comp.lang.c>

3. aka_euGuest

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

aka_eu, Apr 28, 2006
4. Eric SosmanGuest

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.

--

Eric Sosman, Apr 28, 2006

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

6. Default UserGuest

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

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

Default User, Apr 28, 2006
7. Rod PembertonGuest

"aka_eu" <> wrote in message
news:...
> 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

Rod Pemberton, Apr 30, 2006