Combinations of 0 and 1 for a given number of digits in C++

[dparas]

Hello guys,

I ve been searching for a long time for an algorithm (in c++) that would take the number of digits and give all the possible combinations between 0 and 1. For example for number of digits 3 will give

100
010
001
110
101
011
111

The funny thing is, that i think it is simple and well used BUT i cannot find it for days now. Please if anyone could help me in this i would appreciate.

Have a nice day!

Dimitris

[MosaicFuneral]

http://en.wikipedia.org/wiki/Permutation
http://regentsprep.org/regents/Math/permut/Lperm.htm

One way, start at zero and increase(i.e. ++variable; ), till you reaching the target.

[grumpier]

If n is 1, then the set is {0, 1}.

If you have a set for n, the set for n+1 can be generated by appending a 0 and then a 1 to all elements of the set n.

For example, the set for n = 2 will be 0 + {0, 1} and 1 + {0, 1} which becomes {00, 01} and {10, 11} or (more simply) {00, 01, 10, 11}.

An easy method to implement that would involve recursion.

[dparas]

http://en.wikipedia.org/wiki/Permutation http://regentsprep.org/regents/Math/permut/Lperm.htm

One way, start at zero and increase(i.e. ++variable; ), till you reaching the target.

Thank you for your response!
Can you give me an example of what do you mean? Is there any writen code for this?

Thank you again!

[dparas]

If n is 1, then the set is {0, 1}.

If you have a set for n, the set for n+1 can be generated by appending a 0 and then a 1 to all elements of the set n.

For example, the set for n = 2 will be 0 + {0, 1} and 1 + {0, 1} which becomes {00, 01} and {10, 11} or (more simply) {00, 01, 10, 11}.

An easy method to implement that would involve recursion.

Thank you for replying, thats a good approach, i will try to implement it. Do you have a code for this approach btw?

Dimitris

[VernonDozier]

Thank you for replying, thats a good approach, i will try to implement it. Do you have a code for this approach btw?

Dimitris

We can't give you the full code. One thing you need to decide when you use this approach is what you intend to store and how. Both Grumpier and Mosaic Funeral have approaches that will work, but I think they are different approaches, so I would pick one of them and stick with it rather than take a little from each. That's my take on it.

My understanding of Mosaic Funeral's approach is that you would need some helper function that would convert an integer to a string (isolate each binary digit and convert it to a char, then append it to the string). Thus under Mosaic Funeral's approach, there would be no need to store the strings. A helper function could be this:

string BinaryString (int number, int numDigits)
// if passed (14, 4), it would return "1110"

I think Grumpier's approach requires you to take a collection of permutations from n-digits and create all the permutations from n+1 digits from those. So you'd pick whatever storage type you'd want, let's say vector (might not be the best choice, but it could work). A helper function could be this:

vector <string> permutations (vector <string> nPermutations)

So your function could be passed all eight permutations of 3 digits stored as strings and would return all 16 permutations of 4 digits stored as string, for example.

Anyway, that's my sense of it. I'm not sure whether I correctly discerned their ideas, but hopefully I did. Decide which approach you are more comfortable with and go for it. There are other methods too.

[dparas]

We can't give you the full code. One thing you need to decide when you use this approach is what you intend to store and how. Both Grumpier and Mosaic Funeral have approaches that will work, but I think they are different approaches, so I would pick one of them and stick with it rather than take a little from each. That's my take on it.

My understanding of Mosaic Funeral's approach is that you would need some helper function that would convert an integer to a string (isolate each binary digit and convert it to a char, then append it to the string). Thus under Mosaic Funeral's approach, there would be no need to store the strings. A helper function could be this:

string BinaryString (int number, int numDigits)
// if passed (14, 4), it would return "1110"

I think Grumpier's approach requires you to take a collection of permutations from n-digits and create all the permutations from n+1 digits from those. So you'd pick whatever storage type you'd want, let's say vector (might not be the best choice, but it could work). A helper function could be this:

vector <string> permutations (vector <string> nPermutations)

So your function could be passed all eight permutations of 3 digits stored as strings and would return all 16 permutations of 4 digits stored as string, for example.

Anyway, that's my sense of it. I'm not sure whether I correctly discerned their ideas, but hopefully I did. Decide which approach you are more comfortable with and go for it. There are other methods too.

I tried to edit my last post but the time had expired. I made it actually with the first directions of Grumpier's.

Thank you all guys for your help.

Dimitris

[ArkM]

The true funny thing is that it's a VERY simple "algorithm": make a loop from 0 to 2^n-1 and print the binary representation of the loop counter (a very simple thing too).
Don't worry about n > 32: you can't print (or store) more than all 4 billion combinations for n = 32 in practice. If you want to do it, get 64-bit long long counter (in VC++, for example) and buy disk array with more than 10^21 bytes capacity just before ;)...