# iterative combinations

• 06-01-2003
antreas_z
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.
• 06-01-2003
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).
• 06-02-2003
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).
• 06-02-2003
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
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; }```