Combination problem - fast algorithm

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

  1. aka_eu

    aka_eu Guest

    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
    #1
    1. Advertising

  2. aka_eu

    Vladimir Oka Guest

    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>
     
    Vladimir Oka, Apr 28, 2006
    #2
    1. Advertising

  3. aka_eu

    aka_eu Guest

    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
    #3
  4. aka_eu

    Eric Sosman Guest

    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
    #4
  5. 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
     
    Duncan Muirhead, Apr 28, 2006
    #5
  6. aka_eu

    Default User Guest

    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.
     
    Default User, Apr 28, 2006
    #6
  7. "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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. gdogg1587
    Replies:
    3
    Views:
    13,084
    gdogg1587
    Jan 19, 2005
  2. Replies:
    0
    Views:
    672
  3. Michele Simionato

    Python is darn fast (was: How fast is Python)

    Michele Simionato, Aug 23, 2003, in forum: Python
    Replies:
    13
    Views:
    569
  4. Ross

    combination algorithm/source code

    Ross, Dec 9, 2004, in forum: C Programming
    Replies:
    2
    Views:
    610
    Richard Bos
    Dec 9, 2004
  5. Replies:
    8
    Views:
    409
    James Kanze
    Jul 29, 2007
Loading...

Share This Page