Solved

n choose k programming question

Posted on 1998-08-24
10
546 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 84

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
 
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
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 

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 100 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 84

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

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
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…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

744 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now