Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Bitwise shift to generate all possible permutations in C [duplicate]

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).

like image 538
hungrii Avatar asked Sep 17 '11 01:09

hungrii


3 Answers

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

like image 184
evgeny Avatar answered Nov 10 '22 02:11

evgeny


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.

like image 36
dantswain Avatar answered Nov 10 '22 04:11

dantswain


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.

like image 2
supercat Avatar answered Nov 10 '22 04:11

supercat