We help IT Professionals succeed at work.

Check out our new AWS podcast with Certified Expert, Phil Phillips! Listen to "How to Execute a Seamless AWS Migration" on EE or on your favorite podcast platform. Listen Now

x

n choose k programming question

benyamin
benyamin asked
on
Medium Priority
591 Views
Last Modified: 2012-05-04
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
Comment
Watch Question

ozo
CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015

Commented:
What have you got, and what bug does it have?
Does the function have to be recursive?
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.

Author

Commented:
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).
Okay what's the problem benyamin ?  

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

Author

Commented:
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;
}

Author

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

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

Author

Commented:
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.
Commented:
Unlock this solution with a free trial preview.
(No credit card required)
Get Preview

Author

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

Dan
benyamin@ucla.edu
ozo
CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015

Commented:
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);
}

Unlock the solution to this question.
Thanks for using Experts Exchange.

Please provide your email to receive a free trial preview!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.