asked on

n choose k programming question

I am having difficulty implementing an "n choose k" function in C/C++. It seems like it is a recursive function, but mine is buggy for k greater than two.

The function should have parameters like:
nchoosek(int k, int n, int *in, int *out)
where "in" as an array of ints of length n and "out" is the resulting array of length [n!/k!*(n-k)!] *k.

For example, let in=[0 1 2 3] n=4 k=3, then
out=[0 1 2 0 1 3 0 2 3 1 2 3]

I am getting tired of fixing mine!
Thanks,
Dan

ozo

What have you got, and what bug does it have?
Does the function have to be recursive?

Answers2000

If I understand correctly "out" is supposed to be a variable length array allocated inside your function, if yes then you want something like (number of * is significant)

void nchoosek(int k, int n, int *in, int **out, int * numberelem)
{
/* Your code */

/* Setup return array */
*out = (int *)malloc( sizeof(int) * number_of_elements ) ;

/* Setup return value for number of elements */
*numberelem = number_of_elements ;

/* Your code */
}

Call with
int * out ;
int in[] = { 0, 1, 2, 3 } ;
int number ;
nchoosek( 3, 4, &in, &out, &number ) ;

number will now contains the number of elements
out will contain the returned array, you can reference using out[0], out[1], etc.

When done with "out" in your main code do free(out) ;

That should be enough to get you started.

Remember if recursive your calling code can go inside nchoosek.

benyamin

ASKER

The problem is not with calling the function, or memory allocation. "out" can be allocated inside or outside the function...it doesn't matter since the size of "out" is known to the calling function as well (since the size of "out" only depends on n and k).

Answers2000

Okay what's the problem benyamin ?

Give a specific and I'll be happy to help (e.g. consider posting your source)

benyamin

ASKER

Here's code that works for k=2, and can probably be called recursively for larger k, although it get's really messy:

int nchoosek(int k, int n, int *in, int *out){
      int i,l,offset,index=0;

      if(n==1 || n<k)
            return 0;

      for(i=0;i<(n-k+1);i++){

            for(offset=1;offset<(n-i);offset++){

                  out[index]=in[i];
                  index++;

                  out[index]=in[l+i+offset];
                  index++;
                  }
            }
      }

      return 1;
}

benyamin

ASKER

sorry!! :)
The last out statement should be:

out[index]=in[i+offset];

benyamin

ASKER

Never mind, I have fixed the problem. For all interested, you get the nchoosek combinatorial function at

http://pc172.icsl.ucla.edu/benyamin/nchoosek.cpp

I have tried it for n,k up to 8 and it seems to work, but it may still be buggy otherwise.

ASKER CERTIFIED SOLUTION

emmons

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

benyamin

ASKER

Thanks,
For some reason the webserver is down.
E-mail me if you would like the source.

Dan
benyamin@ucla.edu

ozo

for( i=(1<<k)-1; i < 1<<n; ){
int j,l;
for( j=0; 1<<j <= i; j+= 1 ){
if( (1<<j)&i ){ printf("%d ",j); }
}
printf("\n");
j = i&~(i>>1);
j &= -j;
l = i&(j-1);
i += j-l+l/(i&-i);
}