只生成长度为 n 且最多有 k 个连续零的二进制字符串

Question

仅生成长度为 n 且最多有 k 个连续零的二进制字符串的最有效方法是什么。

例如：- 如果 n = 3，k = 2：

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

而不是 000

注意：我的研究 (NLP) 需要这种方法，我在其中使用位串来生成包含所有可能的 n-gram 的句子。我已经尝试枚举所有二进制字符串，但是，由于二进制字符串的数量在句子 2^(n-1) 的长度中呈指数增长，如果 n > 30，代码就会崩溃。因此，我仅限于生成那些具有上述计算可行性条件的位串。

Answer 1

简单递归版本(Delphi)

  procedure Generate(ZeroCount, MaxZeroCount, Len, MaxLen: Integer; s: string);
  begin
    if Len = MaxLen then
      Output(s)
    else begin
      if ZeroCount < MaxZeroCount then
        Generate(ZeroCount + 1, MaxZeroCount, Len + 1, MaxLen, s + '0');
      Generate(0, MaxZeroCount, Len + 1, MaxLen, s + '1');
    end;
  end;

整数值而不是字符串的变体

  if ZeroCount < MaxZeroCount then
    Generate(ZeroCount + 1, MaxZeroCount, Len + 1, MaxLen, Value shl 1);
  Generate(0, MaxZeroCount, Len + 1, MaxLen, (Value shl 1) or 1);

生成的输出(0, 2, 0, 5, '');

只生成长度为 n 且最多有 k 个连续零的二进制字符串

Generate only those binary strings of length n with maximum k consecutive zeros

algorithm

binary

nlp

bits

bitmask