Member Avatar for guest7

Hi,

I wish to generate all the binary combinations for an input size n. So, the number of combinations in this case would be (2^n) and if n=2 my output should be :

00
01
10
11

How can i do it? What would be the best way?

Thanks

  • 5 Contributors
  • 11 Replies
  • 475 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by MosaicFuneral

Dani AI

Generated

A simple, robust pattern that fits the thread: iterate integers 0..(2^n)-1 and build fixed-width binary strings by masking each bit. This avoids floating-point pow() surprises, avoids recursive bit assembly, and makes it trivial to store lines in a vector<string>. Complexity and memory grow as O(2^n * n) so n should remain small.

int n = 4;
size_t total = 1u << n;           // use 1ULL<<n for larger n; ensure n < 32/64 accordingly
std::vector<std::string> combos;
combos.reserve(total);
for (size_t k = 0; k < total; ++k) {
    std::string s(n, '0');
    for (int i = 0; i < n; ++i)
        if (k & (1u << (n - 1 - i)))
            s[i] = '1';
    combos.push_back(s);
}

Concrete fixes and debugging notes tied to the posted code ():

  • Avoid pow(2,n) for integer ranges: pow returns double and may round. Use bit-shift: (1u<<n) or (1ULL<<n) and keep n within the bit-width of the chosen unsigned type.
  • vector<int> ros(comb) pre-fills ros with comb elements; the intended pattern needs an empty container or ros.reserve(n). Likewise vector<vector<int> > col(n) creates n empty rows — declare col empty and reserve if desired.
  • The recursive binary() implementation returns and manipulates a count in a confusing way; iterative bit extraction (shown above) guarantees consistent length and order.
  • Minor bugs that explain an empty/incorrect output: print_vec's inner loop has no itt++ and the call void print_vect(); inside main declares, rather than calls, a function. Correct calling and loop increments are essential.

As pointed out, std::bitset works well when the width is compile-time-fixed; for runtime n consider the string loop above or use boost::dynamic_bitset. As noted, storing the patterns as strings avoids integer-formatting issues when printing leading zeros.

Recommended Answers

All 11 Replies

Member Avatar for Freaky_Chris

Chris

edit: just add one to the number lol and loop through??

Member Avatar for MosaicFuneral

You mean varible++; , or variable += 1; ?
Perhaps you could go to the extreme of doing it with bit operators(I have for fun), or using the inline assembler to do it. So many options, but which is right for you?

Member Avatar for guest7

hi,

could you give me an example of both bit operators and inline assembler.

Thanks

Member Avatar for guest7

Hi,

following is my code.

i wish to store the combinations in a vector as :

000
001
010
011
100
101
110
111

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

int binary(int, vector<int> &);
void print_vec();

int n = 4;	
int comb = pow(2,n)-1;

std::vector<int> ros(comb);
std::vector<vector<int> > col(n);
	
int main() {
	int number;
	cout << comb <<"\n";
	
	for(int k=0; k<=comb; k++)
	{
		number=k;
		if (number < 0) 
			cout << "That is not a positive integer.\n";
		else 
		{
			//cout << number <<" converted to binary is: ";
			int count1=binary(number, ros);
			while(count1<n)
			{
				ros.push_back(0);
				count1++;
			}
			col.push_back(ros);
			ros.clear();
			cout << endl;
		}
	}
	void print_vect();
	return 0;
}

int binary(int number, vector<int> &ros1) 
{
	
	int remainder,count=1;
	if(number <= 1) 
	{
		count = 0;
		ros1.push_back(number);
		//cout << number;
		count++;
	}
	else
	{
		/* There is a right shift operator */
		remainder = number%2;
		count++;
		binary(number >> 1, ros1);    
		//cout << remainder;
		ros1.push_back(remainder);
	}
	return count;
}

void print_vec()
{
	for(int it=0; it<col.size(); it++)
	{
		for(int itt=0; itt<col[it].size(); itt)
		{
			fprintf(stderr,"Here = %d",col[it][itt]);
		}
	}	
}

The problem is my vector is empty when i print it. I am not ale to figure out what is wrong

Thanks

Member Avatar for guest7

if would be great if u can post an example

Member Avatar for mrboolf

Sounds like a subset generating problem to me.

I did almost the same thing a while ago, try reading this.

Hope that helps.

Member Avatar for MosaicFuneral

Why are you making this so complex???

vector<char> container;
    
    cout << "i = 0; i++ till 255" << endl;
    
    for(int i = 0; i < 256; i++)
    {
        container.push_back(i);
        cout << '.';
    }
    
    cout << endl << "Printing: ";
    
    for(int i = 0; i < container.size(); i++)
    {
        cout << bitset<numeric_limits<char>::digits>(container[i]) << endl;
    }
Member Avatar for skatamatic

Are you pushing ints into a vector, or strings? If your pushing 010 into a vector of ints your going to have issues. You're going to need to use stringstream to push numbers into a string then push those onto a vector. The binary numbers themselves can be generated with really simple for loop constructs, as forementioned.

Member Avatar for guest7

Hi,

i am pushing one integer value at a time...So, i am pushing 0, then 1 and so on. Also, i tried the bitset code but the maximum conversion it can do is of integer 255. I think it can convert an integer to a maximum of 8 bits.

Let me know if my understanding is right.

Member Avatar for MosaicFuneral

Just specify the datatype you want in the template parameter, from char to something like short, int, whatever.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.