Enumerating binary sequences

Question

Suppose I wanted to enumerate all 4-bit patterns i.e. from 0 (0000) to 15 (1111). One way is the "truth table" approach:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, ... 1111

This approach is the equivalent of counting up from 0 to 15 in decimal.

Another approach would be using Gray codes, in which only one bit is flipped at a time:

0000, 0001, 0011, 0010, 0110, ... 1000

How would I systematically enumerate all numbers in an order that minimizes the sum of the bits? For example, something along the lines of:

0000, 0001, 0010, 0100, 1000, 0011, 0101, 1001, 0110, 1010, 1001, 0111, 1011, 1101, 1110, 1111

for the 4-bit example.

Ultimately, it would be nice to extend this to any base, but the binary case seems the most straightforward to implement.

EDIT: I probably should have made it clear that the method must be generative i.e. I can't compute all the possible sequences and then sort them; the solution must iteratively produce the sequence in an order similar to the one specified.

Answer 1

This bit-twiddling hack

unsigned next_combination(unsigned x)
{
  unsigned u = x & -x;
  unsigned v = u + x;
  x = v  + (((v ^ x) / u) >> 2);
  return x;
}

will allow you to easily enumerate all unsigned bit-combinations that contain the same number of 1-bits in increasing order. (See https://en.wikipedia.org/wiki/Combinatorial_number_system)

You can use this algorithm to sequentially enumerate all combinations with one 1-bit, two 1-bits, three 1-bits and so on. For example, for combinations up to 4 bits long (as in your example)

#define N 4u

int main()
{
  for (unsigned k = 1; k <= N; ++k)
  {
    for (unsigned subset = (1 << k) - 1; 
         subset < (1 << N); 
         subset = next_combination(subset))
      printf("%X ", subset);

    printf("\n");  
  }
}

http://coliru.stacked-crooked.com/a/0c8327c5e0611eaa

The above Wikipedia link also contains a description of more general algorithm, not relying on any bit-twiddling.

Answer 2

This dumps a list of binary values, sorted by the count of set binary digits (population), ascending. Numbers with equal populations are ranked according to ordinal value.

An array of int values is populated with every unique 4-bit integer.

std::sort sorts the array, using a lambda to compare values. The lambda calls the function population to get a number's set bit count.

Then, the list is output by the function dump_array which converts integer values to std::bitset to get binary representations when sent to std::cout.

#include <iostream>
#include <array>
#include <algorithm>
#include <bitset>


template <typename T>
int population(T x) {  // x<0 => oo loop
    int count = 0;
    while(x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

template <typename A>
void dump_array(const A& a) {
    const char* delim = "";
    for(auto v : a) {
        std::bitset<4> bits(v);
        std::cout << delim << bits;
        delim = ", ";
    }
    std::cout << '\n';
}

int main() {
    std::array<int, 1<<4> vals;
    int i=0;
    for(auto& v : vals) { v = i++; }
    std::sort(vals.begin(), vals.end(), [](int a, int b) {
        const int pop_a = population(a);
        const int pop_b = population(b);
        return pop_a < pop_b || (pop_a == pop_b && a < b);
    });
    dump_array(vals);
}

Answer 3

int main()
{

    int n, p, j, i = 0, sum;
    cin >> n;

    bool *wsk = new bool[n];
    int hmany = static_cast<int> (pow(2, n));
    bool **sortarr = new bool *[hmany];
    for (int i = 0; i < hmany; i++) sortarr[i] = new bool[n];


    bool *wsk1 = wsk;

    for (int i = 0; i < n; i++) *wsk++ = 0;
    wsk = wsk1;

    int z = 0;
    int c = n - 1;
    do
    {

        sum = 0;
        c = n - 1;
        for (int i = 0; i < n; i++)
        {
            if (wsk[i] == 1) sum += static_cast<int>(pow(2,c));
            c--;

        }
        z = sum;

        for (int i = 0; i < n; i++)
        {
            sortarr[z][i] = wsk[i];

        }

        z++; wsk = wsk1;
        i++; p = 0; j = i;

        while (j % 2 == 0)
        {
            j /= 2; p++;

        }

        if (p <= n) wsk[p] = ((1 - wsk[p]) != 0); 


    } while (p < n);

It is all what you wanted.