Member Avatar for 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

  • 5 Contributors
  • 7 Replies
  • 1K Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by ArkM

Dani AI

Generated

The example in Post #1 (seven lines for n=3) omits the all-zero string and is ordered by Hamming weight: all 1-bit patterns (100, 010, 001), then 2-bit patterns (110, 101, 011), then 3-bit (111). That explains why a simple integer counter from 0..2^n-1 (the approach mentioned by and ) would produce a different order (numeric order, including 000). If the sample order is intended, generate combinations by k = number of ones (k = 1..n) rather than raw numeric enumeration.

Implementation notes and tradeoffs: the integer-counter / bit-extraction method streams output with O(1) extra memory and is simplest for full numeric order. A recursive/backtracking approach (as suggested by ) or a k-combinations generator gives natural control over Hamming weight and filtering. ‘s point about storage is important: storing all strings requires O(n * 2^n) memory and becomes impractical quickly (2^20 ~ 1M lines; 2^30 ~ 1B lines). For large n, stream output and avoid building the whole container.

A compact way to reproduce the OP ordering (group by number of 1s, omit all-zero) is to iterate k = 1..n and use a mask with k ones at the front, iterating permutations with std::prev_permutation:

// produce all non-empty n-bit strings grouped by number of 1s
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

void print_by_weight(int n) {
    for (int k = 1; k <= n; ++k) {
        std::vector<int> mask(n, 0);
        std::fill(mask.begin(), mask.begin() + k, 1); // ones at front
        do {
            std::string s; s.reserve(n);
            for (int b : mask) s.push_back(b ? '1' : '0');
            std::cout << s << '\n';
        } while (std::prev_permutation(mask.begin(), mask.end()));
    }
}

Complexity is O(n * 2^n) time overall. To include the all-zero string, start k at 0 (or print the n-zero string first).

Recommended Answers

All 7 Replies

Member Avatar for 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.

Member Avatar for dparas

http://en.wikipedia.org/wiki/Permutation

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!

Member Avatar for 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

Member Avatar for 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.

Member Avatar for 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

Member Avatar for 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 ;)...

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.