iterative combinations

This is a discussion on iterative combinations within the C++ Programming forums, part of the General Programming Boards category; I wrote the following code in order to compute combinations of n per k.Though it works right for number n ...

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    1

    iterative combinations

    I wrote the following code in order to compute combinations of n per k.Though it works right for number n between 1-30 i can't make it work for larger numbers.Does anybody have any idea on how to improve it?

    Code:
    #include <iostream>
    #include <cmath>
    
    using namespace std;
    
    int main() {
    
        int n,c,j,k;
        
        cout<<"Give n:";cin>>n;
        cout<<"Give k:";cin>>k;
    
            /* i goes through all n-bit numbers */
    
        
            for (int 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))
    				
                                cout<<j<<' ';
    			cout<<endl;
                    }
            }
    }
    thanks.

  2. #2
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    for (int i=0; i<(1<<n); i++)

    Thats equivalent to saying 2^n. I know off the top of my head that for a signed integer (normal 32 bit int), anything above n=30 will cause wraparound error (for unsigned 32 bit int, n=31 is the max).
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    You might want to precalculate 1 << n, but that's not that important.

    The overflow issue is more important, but that's always a problem with combinations.
    Another is that the next largest integer type (64-bit) doesn't have the same name on all compilers. On Borland and MS it's called __int64 while on standards compliant compilers (e.g. gcc) it's called long long.

    I usually use boost for that and use the typedef boost::int64_t (or something like that).
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  4. #4
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    You aren't finding all combinations here, but all permutations of 32 bit strings having k ones. The easyest way is to just use next_permutation
    Code:
    #include<vector>
    #include<iostream>
    #include<algorithm>
    #include<stdlib.h>
    
    int main(int argc, char *argv[]) {
        typedef std::vector<bool> bvec;
        typedef bvec::size_type sz_t;
    
        sz_t n=(argc>1)?atoi(argv[1]):4;
        sz_t k=(argc>2)?atoi(argv[2]):2;
        if(k>n) {
            std::cerr << n << " bit number cannot have " << k << " ones";
            std::cerr << std::endl;
            return 2;
        }
        bvec v;
        v.reserve(n);
        v.resize(n-k,false);
        v.resize(n,true);
        do {
            for(sz_t i=0;i<v.size();++i) std::cout << ((v[i])?'1':'0');
            std::cout << std::endl;
        } while(std::next_permutation(v.begin(),v.end()));
        return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. splitting linked list recursive vs. iterative
    By Micko in forum C Programming
    Replies: 7
    Last Post: 03-17-2005, 04:51 PM
  2. Combinations
    By Cmuppet in forum C Programming
    Replies: 6
    Last Post: 10-19-2004, 07:39 AM
  3. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 09:34 PM
  4. Grabbing Ctrl and Alt key combinations
    By scorpio_IITR in forum Linux Programming
    Replies: 0
    Last Post: 04-12-2004, 03:01 AM
  5. Combinations
    By GaPe in forum C Programming
    Replies: 16
    Last Post: 01-09-2002, 04:38 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21