How to efficiently enumerate a Restricted Gray Code?

Question

I'm looking for an algorithm which enumeration all binary strings of length n in a Gray code manner, with the restriction that all strings have at most hamming weight <= k. For example n=4,k=2:

0000
0001
0011
0010
0110
---- skipped
0101
0100
1100
---- skipped
---- skipped
---- skipped
1010
---- skipped
1001
1000

n and k are known constants. The classic Gray code has two very important features: One can simply compute the i-th element a as i ^ (i >> 1) and given the i-th element a one can compute the next one as a ^ ctz(i+1), where ctz returns the number of trailing zeros (gcc buildin function).

So im looking for something like a "restricted" Gray code, with this features, which should be easy and fast computable.

The most straight forward solution would be to insert a popcount into the loop, which branches if a code word has the wrong weight. Sadly this is far to expensive in my setting: n = 45-50 and k = 15-18.

Answer 1

I'm not sure this is what you're looking for but let's give it a try...

The ith element of the code is calculated using the formula you mentioned: G[i] = i ^ (i >> 1). Another feature of the Gray code is that any element is different from the previous one in a single place, therefore the bitwise xor operation between an element G[i] and its predecessor G[i-1], will result in a single bit being equal to one, at the position d at which the two element are different from each other. For instance G[i] ^ G[i-1] = 0101 ^ 0111 = 0010. Now the bitwise and operation between this result and the element G[i], will give 0 only if G[i] has a 0 at position d, otherwise the result will be equal to 2 ^ d, with d starting from 0. So, if (G[i] ^ G[i-1]) & G[i] == 0 it means that at the only place the two elements differ, G[i] has a 0 instead of a 1 and therefore its Hamming weight is 1 less than the one of G[i-1]. On the other hand if (G[i] ^ G[i-1]) & G[i] != 0, the Hamming weight of G[i] is 1 more than the one of G[i-1]. In order to know the Hamming weight of an element you just have to keep track of the weight of the previous elements. Starting from 0 and adding or subtracting 1 each time based on the result of (G[i] ^ G[i-1]) & G[i]. Hopefully this is somewhat comprehensible...

At a first glance I would say that this should perform better than the version using popcount but it may also depend on how operations are implemented both in software and hardware. I'm not particularly expert in this regard.

Here is the code:

#include <stdio.h>
#include <stdint.h>

void printBinary(uint64_t number);   // function for printing the variable in binary

int main()
{
    int k = 18;       // max Hamming weight
    int iter = 1000;  // number of codes to check

    uint64_t Gnew = 0;
    uint64_t Gold = 0;

    int i = 0;
    int count = 0;   // counter holding the Hamming weight of the current element

    printBinary(Gold);   // print the first element (0)

    for (i = 1; i < iter; i++){

        Gnew = i ^ (i >> 1);   // generate the ith element of the Gray code

        if (((Gnew ^ Gold) & Gnew) != 0){   // checks if the new element has one 1 more than the previous
            count++;                        // and increases the counter
        }else{          // or has one 1 less
            count--;    // and decreases the counter
        }
        if(count <= k){    // if element has weight smaller or equal to k print the element
            printBinary(Gnew);
        }

        Gold = Gnew;
    }

    return 0;
}

void printBinary(uint64_t number)    // from https://stackoverflow.com/questions/47326588/c-print-unsigned-int-in-a-binary-base
                                     // with some modifications
{
    int i;

    for(i = 63; i >= 0; i--){
        if(number >> i & 0x1){
                putchar('1');
        }else{
            putchar('0');
        }
    }

    putchar('\n');

    return;
}