?
Solved

n choose k programming question

Posted on 1998-08-24
10
Medium Priority
?
555 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

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

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

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…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
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.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

719 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