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

Question

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

Answer 1

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

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

Answer 3

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.