iterative combinations

[antreas_z]

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?

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

[Zach L.]

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

[CornedBee]

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

[grib]

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

#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;
}