Enumerate all binary numbers of length n and weight at most k lexicographically

Question

I'm looking for an algorithm which enumerates all binary numbers of a given length n lexicoraphically, with the constraint that every number is skipped, which has a hamming weight > k, for a given k.

For example: for n=4 and k=2:

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

of course the most straight forward way would be to add 1 in every loop iterations and check if the hamming weight is over the threshold. But for larger n the number of elements you skip increases, so the overhead of checking every number is increasing too. So I'm also looking for an efficient way to do this.

Update: I reemplented @500-internal-server-error in a iterative way as follows

uint64_t update_stack(uint32_t *stack, uint32_t *sp, const uint64_t n, const uint64_t k) {
    if (stack[*sp] == k) {
        uint32_t i = *sp + 1;

        // walk up
        while (stack[i] == k)
            i += 1;

        // update
        stack[i] += 1;
        const uint32_t val = stack[i];
        const uint32_t altered_sp = i;

        // walk down
        while (i > 0) {
            stack[i - 1] = val;
            i -= 1;
        }

        // fix up stack pointer
        *sp = 0;
        return (1ull << (altered_sp + 1)) - 1;
    } else {
        stack[*sp] += 1;
        return 1ull;
    }
}

void Generate(const uint64_t n, const uint64_t k) {
    uint32_t *stack = (uint32_t *)calloc(n-k+1, sizeof(uint32_t));
    uint32_t sp = 0;

    uint64_t ctr = 0;
    while (ctr < (1ull << n)) {

        // number of k windows the algorithm walks through.
        const uint64_t limit = k+1-stack[sp];

        //print_stack(stack, n, k);

        for (uint64_t cw = limit; cw > 1; --cw) {

            // start printing
            const uint64_t nr_steps = (1ull << cw) - 1ull;
            for (uint64_t i = 0; i < nr_steps; ++i) {
                f(ctr++);
            }

            // skip
            const uint64_t nr_skip = update_stack(stack, &sp, n, k);
            ctr += nr_skip;
        }

        f(ctr++);

        const uint64_t nr_skip = update_stack(stack, &sp, n, k);
        ctr += nr_skip;
    }

    free(stack);
}

which was kinda hard, but it finally worked. I also added a Benchmark, which shows for a simple function f which is applied for every valid value, how much the speedup compared to the naive way. For n=20 and k=3 its 150 times faster (depending on f).

Answer 1

You can do it recursively.

Here's an example in C# (sorry, I am not set up for doing c/c++ right now):

class MainClass
{
    static void Generate(int value, int onesLeft, int bitsLeft, int bits)
    {
        if (bitsLeft > 0)
        {
            Generate(value << 1, onesLeft, bitsLeft - 1, bits);
            if (onesLeft > 0)
                Generate((value << 1) + 1, onesLeft - 1, bitsLeft - 1, bits);
        }
        else
        {
            for (int i = 0; i < bits; i++)
            {
                Console.Write((value >> (bits - i) - 1) & 1);
            }
            Console.WriteLine();
        }
    }

    static void Generate(int bits, int maxOnes)
    {
        Generate(0, maxOnes, bits, bits);
    }

    public static void Main()
    {
        Generate(4, 2);
    }
}

Output for Generate(4, 2):

0000
0001
0010
0011
0100
0101
0110
1000
1001
1010
1100

Output for Generate(5, 1):

00000
00001
00010
00100
01000
10000