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

Question

What is the most efficient way to generate only those binary strings of length n, which have a maximum of k consecutive zeroes.

For eg :- if 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

and not 000

Note : I need this method for my research (NLP), where I am using bit strings to generate sentences with all possible n-grams. I have tried enumerating all the binary strings, however, since the number of binary strings is exponential in the length of the sentence 2^(n-1), the code is crashing if n > 30. Hence, I am limited to only generating those bit-strings with the above condition for computational feasibility.

how about a loop from `0` to `k` using this algorithm? http://stackoverflow.com/questions/1851134/generate-all-binary-strings-of-length-n-with-k-bits-set?rq=1 — גלעד ברקן, Apr 03 '15 at 15:37

MBo · Accepted Answer · 2015-04-04T02:34:41.823

0

Simple recursive version (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;

variant for integer value instead of string

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

output for Generate(0, 2, 0, 5, '');

edited Apr 04 '15 at 02:34

answered Apr 03 '15 at 08:24

MBo

77,366
5
53
86

Thanks @MBo! You are (almost) perfectly right! However, the above code does not yet generate certain strings such as - 00100, 00101 etc. Hence, resetting ZeroCount to 0 in Generate(0, MaxZeroCount, Len + 1, MaxLen, s + '1') helps generate the comprehensive list. Thanks again. – Ashish Shukla Apr 03 '15 at 23:19
Thanks, it's my fault. Fixed. – MBo Apr 04 '15 at 02:35

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

1 Answers1