Computing Combinations on basis of number of bits set

Question

I need to compute all possible combinations of n things selected r at a time where 0<=r<=n, One method to do so is generating the numbers up to 0 to 2^n-1. But I need to generate these numbers such that the numbers should be sorted on the basis of the number of bits set in that number. for n=3:

0         // numbers with 0 bits set

1 2 4     // numbers with 1 bits set

3 5 6     // numbers with 2 bits set

7         // numbers with 3 bits set

I need to know how to generate the numbers such that they are sorted in increasing/decreasing order of bits set?

Answer 1

Iterating over all combinations of some some number of items is covered nicely by quant_dev here.

Answer 2

Implement regular algorithm to generate the combinations, but also hold an additional array where you store the numbers sorted accoding to the 1-bits set. Then for each combination generated replace the numbers with the numbers sitting in the corresponding position minus one in the array sorted as I described.

Answer 3

Here is a simple way function that counts the number of bits set in a number's representation:

// Counts how many bits are set in the representation of the input number n
int numOfBitsSet(int n)
{
    int cnt = 0;
    while (n != 0)
    {
        cnt += (n & 1);
        n = n >> 1;
    }

    return cnt;
}

And here is how you could use it in a (C++11) program that does what you want:

#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>

using namespace std;

int main()
{
    // For instance...
    int n = 3;

    // Fill up a vector of 2^n entries (0 .. 2^(n - 1))
    vector<int> v(1 << n);
    iota(begin(v), end(v), 0);

    // For each number of bits...
    for (size_t i = 0; i <= n; i++)
    {
        cout << "Numbers with " << i << " bits set: ";

        // Find the first number with i bits set...
        auto it = find_if(begin(v), end(v), [i] (int x) { 
            return (numOfBitsSet(x) == i); 
            });

        while (it != end(v))
        {
            cout << *it << " ";

            // Find the next number with i bits set...
            it = find_if(next(it), end(v), [i] (int x) { 
                return (numOfBitsSet(x) == i); 
                });
        }

        cout << endl;
    }
}

If C++11 is not an option for you, you will have to use functors instead of lambdas, and replace std::iota with a manual loop:

#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>

using namespace std;

struct bit_count_filter
{
    bit_count_filter(int i) : _i(i) { }
    bool operator () (int x) const { return numOfBitsSet(x) == _i; }
    int _i;
};

int main()
{
    // For instance...
    int n = 3;

    // Fill up a vector of 2^n entries (0 .. 2^(n - 1))
    vector<int> v(1 << n);
    for (size_t i = 0; i < v.size(); i++)
    {
        v[i] = i;
    }

    // For each number of bits...
    for (size_t i = 0; i <= n; i++)
    {
        cout << "Numbers with " << i << " bits set: ";

        // Find the first number with i bits set...
        auto it = find_if(begin(v), end(v), bit_count_filter(i));
        while (it != end(v))
        {
            cout << *it << " ";

            // Find the next number with i bits set...
            it = find_if(next(it), end(v), bit_count_filter(i));
        }

        cout << endl;
    }
}

Answer 4

You could do it recursively:

void setnbits(unsigned int cur, int n, int toset, int max)
{
    if(toset == 0)
    {
        printf("%d ", cur >> (n + 32 - max) , n);
        return;
    }
    toset--;
    for(int i = 1 ; i <= n-toset ; i++)
    {
        setnbits((cur >> i) | 0x80000000, n-i, toset , max);
    }
}

Could be called like:

for(int z = 0 ; z < 4 ; z++)
{
    printf("%d bits: ", z);
    setnbits(0, 3, z, 3);
    printf("\n");
}

prints:

0 bits: 0
1 bits: 1 2 4
2 bits: 3 5 6
3 bits: 7

The numbers are not guaranteed to be in numerical order.

Answer 5

That's pretty easy. There are two cases:

1) Last 1-bit has 0-bit before: 000111001001 -> 000111001010.

You should just move it to the left

2) There is a chain of 1-bits: 000110111100 -> 000111000111

Then you should move last 1-bit to the nearest 0-bit on the left(before the chain), and move all another bits of that chain to the right.

You'll get this way all needed numbers in increasing order.