按字典序枚举所有长度为n，权重至多为k的二进制数

Question

我正在寻找一种算法，该算法按字典序枚举给定长度 n 的所有二进制数，并限制每个数字都被跳过，它具有汉明权重 > k，对于给定 k.

例如：对于n=4和k=2：

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

当然，最直接的方法是在每次循环迭代中加 1 并检查汉明权重是否超过阈值。但是对于更大的 n ，您跳过的元素数量会增加，因此检查每个数字的开销也会增加。所以我也在寻找一种有效的方法来做到这一点。

更新：我以如下迭代方式重新填充了@500-internal-server-error

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);
}

这有点难，但终于奏效了。我还添加了一个 Benchmark，它显示了一个应用于每个有效值的简单函数 f，与原始方法相比加速了多少。对于 n=20 和 k=3 它快 150 倍（取决于 f）。

Answer 1

你可以递归地做。

这是一个 C# 示例（抱歉，我现在还没有准备好执行 c/c++）：

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);
    }
}

生成 (4, 2) 的输出：

Generate(5, 1) 的输出：

按字典序枚举所有长度为n，权重至多为k的二进制数

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

c

combinatorics