12

Possible Duplicate:
Creating multiple numbers with certain number of bits set

I'm attempting to write some code which will put each possible combination of numbers in an array by shifting the bits across.

For example, I wanted to find all possible combinations of 3 bits (where the max a digit can be is 6) the array should contain: 

000111
001011
001101
001110
010011
010101
010110
011001
011010
011100
100011

And so on...

From what I've interpreted, when the last position bit is 1 we shift the number by 1 (x >> 1) and add a 1 at the start. However, I'm unsure how to code the rest. I'm using C to write this.

Also - as far as I can tell this is a colex sequence, however, I'm all ears if there is another sequence that will give me the same end result (array with all possible combinations of k-bits with a constraint of N).

Community
  • 1
  • 1
hungrii
  • 145
  • 1
  • 4
  • 4
    Dup of [Creating multiple numbers with certain number of bits set](http://stackoverflow.com/questions/506807/creating-multiple-numbers-with-certain-number-of-bits-set), [Generate all binary strings of length n with k bits set](http://stackoverflow.com/questions/1851134/generate-all-binary-strings-of-length-n-with-k-bits-set). – outis Sep 17 '11 at 01:52

3 Answers3

6

You can solve this by generating the sequences recursively.

Let us define a recursive function f(int index, int bits, int number) that will take in the current index of the bit and the number of bits left to place, and the number generated so far. Then, you have the option of setting the current bit to 1 or to 0, and recursing from there.

Overall, the time complexity should be O(number of sequences), or O(N choose B), where N is the number of digits and B is the number of bits set to 1.

The function goes something like this:

void f(int index, int bits, int number) {
    if (index == 0) {
        if (bits == 0) {   // all required bits have been used
            emit_answer(number); // chuck number into an array, print it, whatever.
        }   
        return;
    }   

    if (index-1 >= bits) {  // If we can afford to put a 0 here
        f(index-1, bits, number);
    }   

    if (bits > 0) {  // If we have any 1s left to place
        f(index-1, bits-1, number | (1 << (index-1)));
    }   
}

// to call:
f(6, 3, 0);

For N,B = 6,3 the output matches yours, and is in sorted order. Link to working example: http://codepad.org/qgd689ZM

evgeny
  • 2,564
  • 17
  • 27
  • Thanks @evgeny. Played around with this and learnt a few things. Just regarding the dupe - for those that are interested, follow the dupe link and read the Stanford resource. Helped me greatly. – hungrii Sep 17 '11 at 14:38
2

There's probably a more efficient way, but you could just loop through the numbers and reject numbers that don't have a bit count of 3? See this answer for bit counting.

Community
  • 1
  • 1
dantswain
  • 5,427
  • 1
  • 29
  • 37
  • Then you have to go through 2^N combinations which can get pretty slow. Then again, he only needs it for 6 bits so it should be fine. – flight Sep 17 '11 at 01:51
  • This is pretty slow, O(2^N) like quasiverse pointed out. My solution should generate all valid sequences without any waste. – evgeny Sep 17 '11 at 01:56
  • 1
    OK, sure. It's O(2^6). Though, I'd argue that if speed is really an issue he could calculate the numbers ahead of time and save them. Then it would be O(1) :-p Not to mention the readability of this solution vs some of the others. *shrug* – dantswain Sep 17 '11 at 02:28
2

No need for any fancy recursion. Some simple math will suffice (a division by a value which will always be a power of two is required).

    Function nextBits(ByVal prevVal As Integer)
        Dim lsOne As Integer = ((prevVal - 1) And Not prevVal) + 1
        Dim nextZero As Integer = (prevVal + lsOne) And Not prevVal
        Dim lowBits As Integer = ((nextZero \ lsOne \ 2) - 1)
        Return prevVal + lsOne + lowBits
    End Function

Nice and easy.

supercat
  • 77,689
  • 9
  • 166
  • 211
  • 2
    Uhh... my brain is hurting from the code. Also, what's the \ operator? And perhaps an explanation of why this works would help. – flight Sep 17 '11 at 02:17
  • Please add more explanation to the code. OP seems to be interested in C code and this rather seems like VB-ish. – Hritik Oct 20 '18 at 16:21
  • Sorry. I tested the algorithm in VB.NET and copy/pasted the code. The same algorithm should be readily adaptable to any other common language. An aspect of VB.NET I forgot that people wouldn't know is that it uses a different operator for fractional division and whole-number division, so `15 / 4` yields 3.75, but `15 \ 4` yields 3. The Python equivalent would be the `//` operator, and the C equivalent is the `/` operator with integer operands (necessitating an explicit cast or coercion if one wants to divide two integers to get a fractional result). – supercat Oct 20 '18 at 18:14
  • @Hritik: I thought the question had seemed like it might be homework-ish, so I figured I wanted to steer the person in the right direction without giving a solution they could use without thinking or understanding. Trying some different values and seeing what each variable ends up being in binary should reveal what's going on. – supercat Oct 20 '18 at 18:18