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