I would like to generate all binary string with no more than K consecutive 1's (see example below). The naive approach seems easy to me but O(2^N) time complexity is quite slow. However, I'm sure I can solve it using DP, because it seems almost like Fibonacci problem. Unfortunately, I can't figure it out how to do this. At best, I suppose it is possible to get O(P), where P is a number of wanted binary strings.

Example for N=4, K=2:

0000, 0001, 0011, 0010, 0100, 0101, 1000, 1001, 1010, 1011, 1100, 1101.

Remark: A similar question has been raised a couple of times here but answers were either naive (O(2^N)) or only generated for exactly K 1's in a row.

CodePudding user response：

You mention that

1. the naive approach has O(2^N) complexity
2. "at best, it is possible to get O(P), where P is a number of wanted binary strings"

Considering a case where K = N-1, there will actually be 2^N - 1 sequences. Any algorithm that generates all these sequences can't have better than O(2^N) performance.

That being said, you could define a simple recurrence relation to "prune" out the cases that can't lead to a valid sequence.

generate(n, k, curr_string, consecutive_ones):
    if consecutive_ones > k: return
    if length of curr_string == n: add curr_string to the answer

    # first recurrence to add 0
    generate(n, k, curr_string   "0", 0)

    # first recurrence to add 1
    generate(n, k, curr_string   "1", consecutive_ones 1)

CodePudding user response：

You could just generate the sequences directly, without the other (invalid) sequences of length N. The code below shows how to do this in Python with recursion and generators, but the same logic can be done iterative, and without generators (using an explicit stack instead).

def gen(n, k, p=0):
    if n == 1:
        yield [0]
        if p < k:
            yield [1]
        return
    for seq in gen(n-1, k, 0):
        yield [0]   seq
    if k == p:
        return
    for seq in gen(n-1, k, p 1):
        yield [1]   seq

Example output:

>>> from pprint import pprint
>>> pprint(list(gen(4, 2)))
[[0, 0, 0, 0],
 [0, 0, 0, 1],
 [0, 0, 1, 0],
 [0, 0, 1, 1],
 [0, 1, 0, 0],
 [0, 1, 0, 1],
 [0, 1, 1, 0],
 [1, 0, 0, 0],
 [1, 0, 0, 1],
 [1, 0, 1, 0],
 [1, 0, 1, 1],
 [1, 1, 0, 0],
 [1, 1, 0, 1]]

What the code generator does is produce an series of length n lists with at most k consecutive 1's, assuming a prefix of p 1's. At the base case, it returns a list of just one element, for the recursive case, it gets the appropriate subsequences, and prefixes them with 0 or 1.