Restricted randomization of a binary vector

What you could do (in close to O(n) time, if I'm not mistaken) is, parameterizing it with "limit", prepare / pre-compute an epsilon-free context-free grammar such as (for limit = 3),

Upto3 -> LimitOnes | LimitZeros
LimitOnes -> Zeros Ones LimitOnes | Zeros Ones | Zeros
LimitZeros -> Ones Zeros LimitZeros | Ones Zeros | Ones
Zeros -> Zero | Zero Zero | Zero Zero Zero
Ones -> One | One One | One One One
Zero -> 0
One -> 1

(please note: I don't claim it's the correct or simplest grammar you will want you use, but you can always fiddle / experiment with your own using the nifty Grammophone tool, by Michael Daines)

where "Upto3" is the grammar's axiom / start symbol.

(The only two rules depending on N being Zeros -> ... and Ones -> ...)

Then, using such a pre-computed grammar (that you'll use for generation purposes instead of parsing), you can write a simple recursive function, which, starting from the start symbol, randomly picks one of the alternatives of the rules and applies it, by string concatenation, on an accumulator that it passes to itself (and that you'll have passed as the empty string for the top level call).

At each recursive call, it is trivial to decide (depending on N and the last known length of the accumulator) which alternative branch of the rules (aka, productions) -- LimitOnes, LimitZeros, Ones, or Zeros -- it is meaningful to follow (to not exceed N).

Eg,

N = 10, limit = 3:

start with Upto3 : accumulator = ""

from "Upto3", randomly pick "LimitZeros"

from "LimitZeros", apply "Ones", "Zeros" in "Ones Zeros LimitZeros" : accumulator = "100"

from "LimitZeros", apply "Ones", "Zeros" in "Ones Zeros LimitZeros" : accumulator = "100110"

etc, etc.

I let you figure out the implementation details.

'Hope this helps,

The general approach to tackle a problem of this kind is to think about the combinatorics. How would you answer the question "How many 40-bit binary strings are there with no runs of more than 3 of the same bit?"

Answer: structural decomposition. A 40-bit binary string with no runs of more than 3 of the same bit ends in a run of 1, 2, or 3 bits; in general we can define a function f(n) counting n-bit binary strings which no run of more than 3 bits, and derive the recurrence f(1) = 1, f(0) = 1 (very important!), f(-1) = 0, and for larger n, f(n) = f(n-1) + f(n-2) + f(n-3).

Now, extend that to the question "How many 40-bit binary strings are there with Hamming weight of 20 bits and no runs of more than 3 of the same bit?". This time the structural decomposition needs to take into account the Hamming weight by some means or other. One way would be to consider the excess of the final bit: e.g. in 0010110 the final bit is 0 and the excess is 1 because there is one more 0 than 1. This time let's call our function g. We want to know g(40, 0) (40-bit string with 0 excess).

To derive the recurrence for g(n, e) we first suppose that the final run is of length r. If the total number of bits of the same value as the final run is b and the number of the other bit is a then by definition e = b - a. If we remove the run, we're left with n - r bits and the subtraction for the excess flips (remember that it's the excess of the last bit, and by removing the final run we flip the last bit) to become a - (b - r) = r - e.

So we get the recurrence g(n, e) = g(n - 1, 1 - e) + g(n - 2, 2 - e) + g(n - 3, 3 - e). Base cases are left as a detail which must be filled in.

Note that we can use a standard dynamic programming table approach to calculate g(n, e) in O(ne) space and time.

Having filled that table, we can address the original question: how to generate one of the g(40, 0) strings. We simply decide whether the final run will be of 0 or 1 (by a simple call to rand()), and decide whether it will be of length 1, 2, or 3 (ideally weighting the random choice in proportion to the contributions of each of the three: g(n - r, r - e)). Then we step down to that g(n', e') and apply the same process with the minor difference that rather than randomly deciding the value of the final run we flip it from the suffix.

The key point I want to make is that this process of first using a structural decomposition to answer the combinatoric question is a very general technique which applies to many many combinatorial structures. You can use it to uniformly generate a random partition of an integer, a random binary tree with a given number of nodes, etc.

Consider the following approach:

1. Create a random vector without limitations
2. Use a predefined line code in a way similar to 4B5B (https://en.m.wikipedia.org/wiki/4B5B) to make the above satisfy your limitations.

There is a general problem in the area of communication, there are many reasons for which we want to transform a string of bits into another string such that the amount of repetitions of each bit is limited (e.g avoid long substring that is all zeros or all ones). I am certain that if you review the subject you'll find what you're looking for,I believe that the 4B5B method can be generalized to achieve what you need as well, so that's a good starting point