bit-twiddling for do combination

/* This program accepts n and k on the command line, then prints
* all n C k combinations of integers from 1..n
*/
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *argv[]) {
        int     n, k, i, j, c;

        if (argc != 3) {
                printf ("Usage: %s n k\n", argv[0]);
                exit (1);
        }
        n = atoi (argv[1]);
        k = atoi (argv[2]);

    /* i goes through all n-bit numbers */

        for (i=0; i<(1<<n); i++) {

        /* masking the j'th bit as j goes through all the bits,
         * count the number of 1 bits.  this is called finding
         * a population count.
         */
                for (j=0,c=0; j<32; j++)
                {
                    if (i & (1<<j))
                    {
                        c++;
                    }
                }

        /* if that number is equal to k, print the combination... */
                if (c == k) {

            /* by again going through all the bits indices,
             * printing only the ones with 1-bits
             */
                     for (j=0;j<32; j++)
                     {
                          if (i & (1<<j))
                          {
                               printf ("%i ", j+1);
                          }     
                     }
                      printf ("\n");
                }
        }
        exit(0);
}

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s