8

How can I generate all possible bit combinations in an array of bits of length n. If I start with all zeros in my array then there are n possibilities to place the first bit and for these n possibilities there are n-1 possibilities to place the second bit.. unit all n bits are set to one. But so far I didn't manage to program it out.

Also many people pointed out that I can do this by counting from 0 to (2^n)-1 and printing the number in binary. This would be an easy way to solve the problem, however in this case I just let the machine counting instead of telling it where to place ones. I do this for learning, so I would like to know how to program out the ones-placing approach.

Johannes Schaub - litb
  • 496,577
  • 130
  • 894
  • 1,212
Nils
  • 13,319
  • 19
  • 86
  • 108
  • @Fred if I know a lisp answer and a C# answer am I allowed to add "[lisp]" and "[c#]" or should we just replace all those by "[language-agnostic]"? – Johannes Schaub - litb Jan 08 '11 at 11:48
  • @Johannes: I would love to see LISP and C# solutions :-) I added the C++ tag because Nils posted the question in the C++ chat, so I assumed he was interested in a C++ solution. And I added the Haskell tag so real Haskell programmers could improve my Haskell solution. – fredoverflow Jan 08 '11 at 12:01

7 Answers7

13

How would you count manually on paper? You would check the last digit. If it is 0, you set it to 1. If it is already 1, you set it back to 0 and continue with the next digit. So it's a recursive process.

The following program generates all possible combinations by mutating a sequence:

#include <iostream>

template <typename Iter>
bool next(Iter begin, Iter end)
{
    if (begin == end)      // changed all digits
    {                      // so we are back to zero
        return false;      // that was the last number
    }
    --end;
    if ((*end & 1) == 0)   // even number is treated as zero
    {
        ++*end;            // increase to one
        return true;       // still more numbers to come
    }
    else                   // odd number is treated as one
    {
        --*end;            // decrease to zero
        return next(begin, end);   // RECURSE!
    }
}

int main()
{
    char test[] = "0000";
    do
    {
        std::cout << test << std::endl;
    } while (next(test + 0, test + 4));
}

The program works with any sequence of any type. If you need all possible combinations at the same time, just put them into a collection instead of printing them out. Of course you need a different element type, because you cannot put C arrays into a vector. Let's use a vector of strings:

#include <string>
#include <vector>

int main()
{
    std::vector<std::string> combinations;
    std::string test = "0000";
    do
    {
        combinations.push_back(test);
    } while (next(test.begin(), test.end()));
    // now the vector contains all pssible combinations
}

If you don't like recursion, here is an equivalent iterative solution:

template <typename Iter>
bool next(Iter begin, Iter end)
{
    while (begin != end)       // we're not done yet
    {
        --end;
        if ((*end & 1) == 0)   // even number is treated as zero
        {
            ++*end;            // increase to one
            return true;       // still more numbers to come
        }
        else                   // odd number is treated as one
        {
            --*end;            // decrease to zero and loop
        }
    }
    return false;              // that was the last number
}
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
  • This algorithm is not recursive, it's just iterative. Instead of recursing, you could just jump back to the start -- using a recommended control structure, of course :-) A smart compiler might recognise this, but it might not. Of course, the running time is exponential in n, and the stack growth is only linear; so the program will work. But unnecessary recursion is generally a bad thing. – TonyK Jan 08 '11 at 11:34
  • Very nice algorithm...but is there a better explanation to this algorithm..may be some slides showing its working!! – anand Jan 10 '14 at 10:33
11

Such problems are trivially solved functionally. To find the solutions of length n, you first find the solutions of length n-1 and then append '0' and '1' to those solutions, doubling the solution space.

Here is a simple recursive Haskell program:

comb 0 = [[]]

comb n =
    let rest = comb (n-1)
    in  map ('0':) rest
     ++ map ('1':) rest

And here is a test run:

> comb 3
["000","001","010","011","100","101","110","111"]
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
2

A "truly" recursive approach in C++:

#include <iostream>
#include <string>

void print_digits(int n, std::string const& prefix = "") {
    if (!n) {
        std::cout << prefix << std::endl;
        return;
    }
    print_digits(n-1, prefix + '0');
    print_digits(n-1, prefix + '1');
}

int main(int, char**) {
    print_digits(4);
}
etarion
  • 16,935
  • 4
  • 43
  • 66
1

Optimal solution is here:

http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

R.. GitHub STOP HELPING ICE
  • 208,859
  • 35
  • 376
  • 711
1

This is my answer. The advantage is that all the combinations are saved in a two dimension array, but the disadvantage is that you can only use it for a sting long up to 17 digits!! 

#include <iostream>

using namespace std;

int main()
    {
    long long n,i1=0,i2=0, i=1, j, k=2, z=1;
    cin >> n;
    while (i<n){
        k = 2*k;
        i++;
    }
    bool a[k][n], t = false;
    j = n-1;
    i1=0;
    i2 = 0;
    z = 1;
    while (j>=0){
        if(j!=n-1){
        z=z*2;
        }
        i2++;
        t = false;
        i = 0;
    while (i<k){
        i1 = 0;
        while (i1<z){
            if(t==false){
            a[i][j]=false;
            }
            else {
                a[i][j]= true;
            }
            i1++;
            i++;
        }
        if(t==false){
            t = true;
        }else {
            t = false;
        }
    }
    j--;
    }
    i = 0;
    j = 0;
    while (i<k){
        j = 0;
        while (j<n){
            cout << a[i][j];
            j++;
        }
        cout << endl;
        i++;
    }
    return 0;
}
stealthyninja
  • 10,343
  • 11
  • 51
  • 59
OPMagicPotato
  • 215
  • 1
  • 2
  • 7
0

FredOverflow is right in general.

However, for 1s & 0s you'd better just increment an integer from 0:

int need_digits = 10
unsigned int i=0
while (! i>>need_digits){
    # convert to binary form: shift & check, make an array, or cast to string, anything.
    }

... i guess you won't need more than 32 bits or you'd have to chain multiple integers.. and stick to the previous answer :)

kolypto
  • 31,774
  • 17
  • 105
  • 99
  • 1
    +1 for the simplicity of the approach. However, that loop condition is grim; please use `(for i = 0; i < (1L << need_digits); i++)` or similar! – Oliver Charlesworth Jan 08 '11 at 11:34
  • for learning you'd better try not to limit the task with 1s&0s, try generating numbers like [a..c][a..d][a..z] and such ;) – kolypto Jan 08 '11 at 12:12
0

regex is your best friend for these. here's a reasonably fast method not specific to any language (code here is awk, but concept is very portable):

  • using regex to generate every bit-string comboall the way to 2^28 in less than 2.946 secs

  • if you only need every 2^16 combo, it's less than 0.5 secs

  • they're all pre-sorted in big-endian sequential order, in a single string : so just cut out what you need from there.

  • as you can see from gawk profiler - it only requires 1 loop per bit-level.

    • strip away the timer() and printf() parts and it all boils down to just :

~

  1     ____=_=(_<_)(___^=_)
  1          __="."
  1     gsub(__,"\\&&",____)

  15    while (___++<+BITS_NEEDED) {
  15        gsub(__,____,_)
  15        __=__"."
        }

_

using mawk2

 #bits :  2 |   0.00260 secs |          4 segs | 8             bitstr-len | 00011011
 #bits :  3 |   0.00504 secs |          6 segs | 18            bitstr-len | 000000011100110111
 #bits :  4 |   0.00749 secs |         10 segs | 39            bitstr-len | 001001110001111001100001101111
 #bits :  5 |   0.00979 secs |         17 segs | 84            bitstr-len | 101110011100001100000011011111
 #bits :  6 |   0.01197 secs |         30 segs | 183           bitstr-len | 001100100001101100000110111111
 #bits :  7 |   0.01445 secs |         56 segs | 391           bitstr-len | 011000001101011000001110111111
 #bits :  8 |   0.01672 secs |        105 segs | 841           bitstr-len | 100001110111110000011101111111
 #bits :  9 |   0.01896 secs |        199 segs | 1793          bitstr-len | 001110111111000000111011111111
 #bits : 10 |   0.02119 secs |        379 segs | 3788          bitstr-len | 110001111110000001110111111111
 #bits : 11 |   0.02348 secs |        724 segs | 7967          bitstr-len | 110011111100000011101111111111
 #bits : 12 |   0.02578 secs |       1390 segs | 16684         bitstr-len | 100111111000000111011111111111
 #bits : 13 |   0.02896 secs |       2678 segs | 34809         bitstr-len | 001111110000001110111111111111
 #bits : 14 |   0.03210 secs |       5171 segs | 72393         bitstr-len | 011111100000011101111111111111
 #bits : 15 |   0.03505 secs |      10009 segs | 150142        bitstr-len | 111111000000111011111111111111
 #bits : 16 |   0.03781 secs |      19414 segs | 310629        bitstr-len | 111110000001110111111111111111
 #bits : 17 |   0.04070 secs |      37723 segs | 641289        bitstr-len | 111100000011101111111111111111
 #bits : 18 |   0.04417 secs |      73414 segs | 1321444       bitstr-len | 111000000111011111111111111111
 #bits : 19 |   0.04904 secs |     143073 segs | 2718379       bitstr-len | 110000001111011111111111111111
 #bits : 20 |   0.05737 secs |     279184 segs | 5583670       bitstr-len | 100100001111011111111111111111
 #bits : 21 |   0.07305 secs |     545413 segs | 11453681      bitstr-len | 001000011110111111111111111111
 #bits : 22 |   0.09946 secs |    1066640 segs | 23466075      bitstr-len | 010000111101111111111111111111
 #bits : 23 |   0.15100 secs |    2087981 segs | 48023565      bitstr-len | 110000111101111111111111111111
 #bits : 24 |   0.25276 secs |    4090896 segs | 98181495      bitstr-len | 100001111011111111111111111111
 #bits : 25 |   0.45808 secs |    8021635 segs | 200540878     bitstr-len | 100001111011111111111111111111
 #bits : 26 |   0.79723 secs |   15741040 segs | 409267048     bitstr-len | 100001111011111111111111111111
 #bits : 27 |   1.49781 secs |   30910510 segs | 834583780     bitstr-len | 000011110111111111111111111111
 #bits : 28 |   2.91132 secs |   60737902 segs | 1700661245    bitstr-len | 000011110111111111111111111111
( LC_ALL=C mawk2 -v BITS_NEEDED='28' ; )  2.54s user 0.35s system 98% cpu 2.946 total

CODE, and output using gawk

 #bits :  2 |   0.00272 secs |          4 segs | 8             bitstr-len | 00011011
 #bits :  3 |   0.00531 secs |          8 segs | 24            bitstr-len | 000001010011100101110111
 #bits :  4 |   0.00906 secs |         16 segs | 64            bitstr-len | 001001101010111100110111101111
 #bits :  5 |   0.01170 secs |         32 segs | 160           bitstr-len | 110101101111100111011111011111
 #bits :  6 |   0.01425 secs |         64 segs | 384           bitstr-len | 111011111100111101111110111111
 #bits :  7 |   0.01687 secs |        128 segs | 896           bitstr-len | 111111100111110111111101111111
 #bits :  8 |   0.01943 secs |        256 segs | 2048          bitstr-len | 111100111111011111111011111111
 #bits :  9 |   0.02203 secs |        512 segs | 4608          bitstr-len | 100111111101111111110111111111
 #bits : 10 |   0.02476 secs |       1024 segs | 10240         bitstr-len | 111111110111111111101111111111
 #bits : 11 |   0.02799 secs |       2048 segs | 22528         bitstr-len | 111111011111111111011111111111
 #bits : 12 |   0.03193 secs |       4096 segs | 49152         bitstr-len | 111101111111111110111111111111
 #bits : 13 |   0.03501 secs |       8192 segs | 106496        bitstr-len | 110111111111111101111111111111
 #bits : 14 |   0.03909 secs |      16384 segs | 229376        bitstr-len | 011111111111111011111111111111
 #bits : 15 |   0.04370 secs |      32768 segs | 491520        bitstr-len | 111111111111110111111111111111
 #bits : 16 |   0.04993 secs |      65536 segs | 1048576       bitstr-len | 111111111111101111111111111111
 #bits : 17 |   0.05996 secs |     131072 segs | 2228224       bitstr-len | 111111111111011111111111111111
 #bits : 18 |   0.07843 secs |     262144 segs | 4718592       bitstr-len | 111111111110111111111111111111
 #bits : 19 |   0.11286 secs |     524288 segs | 9961472       bitstr-len | 111111111101111111111111111111
 #bits : 20 |   0.17921 secs |    1048576 segs | 20971520      bitstr-len | 111111111011111111111111111111
 #bits : 21 |   0.31018 secs |    2097152 segs | 44040192      bitstr-len | 111111110111111111111111111111
    # gawk profile, created Thu Jun  2 05:36:49 2022

    # BEGIN rule(s)

    BEGIN {
     1      ____ = _ = "01"
     1      __ = "."
     1      srand()
     1      ______ = timer()
     1      gsub(__, "\\&&", ____)
     1      ++___
    20      while (___++ < +BITS_NEEDED) {
    20          gsub(__, ____, _)
    20          print sprintf(" #bits : %2.f | %9.5f secs | %10.f segs | %-13.f bitstr-len | %.30s%.0s", ___, (timer() - ______) / (1E6 - 1E-6), (_____ = length(_)) / ___, _____, substr(_, ++_____ - 30), __ = __ ".")
        }
    }


    # Functions, listed alphabetically

    21  function timer(_, __)
    {
    21      return (substr("", (__ = "gdate +'%s%6N'") | getline _, close(__)) _)
    }
( LC_ALL=C gawk -p- -v BITS_NEEDED='21' -b -e ; )  0.26s user 0.04s system 93% cpu 0.321 total
RARE Kpop Manifesto
  • 2,453
  • 3
  • 11