列举所有长度为n和重量的二元数量，最多是k词典

Question

我正在寻找一种算法，该算法列举了给定长度的所有二进制n词典，并限制了每个数字都被跳过，其中具有锤击权重＆gt; 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);
}

这很难，但最终奏效了。我还添加了a benchmark 适用于每个有效值，与幼稚方式相比的加速度。对于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）的输出：

0000
0001
0010
0011
0100
0101
0110
1000
1001
1010
1100

生成（5，1）的输出：

00000
00001
00010
00100
01000
10000