Solved

n choose k programming question

Posted on 1998-08-24
10
549 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
DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

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

ScreenConnect 6.0 Free Trial

Explore all the enhancements in one game-changing release, ScreenConnect 6.0, based on partner feedback. New features include a redesigned UI, app configurations and chat acknowledgement to improve customer engagement!

Question has a verified solution.

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

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

770 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