Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

n choose k programming question

Posted on 1998-08-24
10
Medium Priority
?
559 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
0
Comment
Question by:benyamin
  • 5
  • 2
  • 2
  • +1
10 Comments
 
LVL 85

Expert Comment

by:ozo
ID: 1252285
What have you got, and what bug does it have?
Does the function have to be recursive?
0
 
LVL 8

Expert Comment

by:Answers2000
ID: 1252286
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.
0
 

Author Comment

by:benyamin
ID: 1252287
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).
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 8

Expert Comment

by:Answers2000
ID: 1252288
Okay what's the problem benyamin ?  

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

Author Comment

by:benyamin
ID: 1252289
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;
}
0
 

Author Comment

by:benyamin
ID: 1252290
sorry!! :)
The last out statement should be:

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

Author Comment

by:benyamin
ID: 1252291
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.
0
 
LVL 4

Accepted Solution

by:
emmons earned 300 total points
ID: 1252292
I can't get at your source, but one of the things that leaps out is that you will need to deal with all of the memory allocations. A quick routine to tell you how many answers will be in the final result would be

long fact(long n); //function prototype
long n_take_k(long n, long k); //function definition

int main( int argc, char ** argv)
{
      long answer,n,k;
        sscanf( argv[1], "%d", &n);
        sscanf( argv[1], "%d", &k);
//      cin>>n>>k;
      answer = n_take_k( n, k);
        printf( "%ld take %ld = %ld\n", n, k, answer
      cout<<answer;
      return 0;
}
 
long n_take_k(long n, long k)
{
      return fact(n)/(fact(k)*fact(n-k));
}

long fact(long n)
{
      long product = 1;
      for (int i=n; i>1; i--)
            product = product*i;
      return product;
}

0
 

Author Comment

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

Dan
benyamin@ucla.edu
0
 
LVL 85

Expert Comment

by:ozo
ID: 1252294
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);
}

0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
Suggested Courses
Course of the Month15 days, 19 hours left to enroll

580 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question