Limit repetitions in randomized list with each unique element occurring n times

Question

I have a set of 3 elements and need to generate a randomized sequence containing each element n times with the condition that one element can only occur m times in a row.

So with elements [0,1,2] n = 4 and m = 3:
[1, 2, 0, 0, 0, 1, 1, 2, 2, 2, 0, 1] valid
[1, 2, 0, 0, 0, 0, 1, 2, 2, 2, 1, 1] invalid

The only solutions I found were to add all elements n times to a list and then shuffle until the condition is satisfied or generate the whole search space and then randomly sample from the correct solutions. Both seem possibly slow and memory intensive.
Could just be looking for the wrong terms, this has to be documented somewhere.

I came up with this approach, but am not sure about correctness.

E: set of elements e
n: of each element in sequence
m: maximum repetitions of one element
S = [] # empty sequence
while |S| < |E| * n:
    R = shuffled list containing each e m times
    for m:
        if s+r satisfies condition:
            S <- s+r # Extend s with r
        else:
            rotate r by one element
return the first |E| * n elements of S

It seems to produce correct results, but is it ok to sample and then rotate the subsequences R like that?
Would the time complexity be just O(|E| * n * m)?

Here is my python implementation:

def generate_sequence(e, n, m):
# Final sequence
s = []
# Extend s by n * len(elements) each iteration
for _ in range(n//m+1):
    r = list(e) * m
    random.shuffle(r)
    for _ in range(len(r)):
        # List of all windows of size m+1 where at least one element is from s or r.
        windows = filter(lambda x: len(x) == m + 1,
                         [s[-i:] + r[:(m + 1 - i)] for i in range(1, m + 1)])
        # check if any window contains an invalid sequence
        if not all(len(set(window)) > 1 for window in windows):
            # rotate r one to right
            r = [r[-1]] + r[:-1]
        else:
            # Valid s+r
            s.extend(r)
            break
return s[:len(list(e)) * n]

Answer 1

I will assume that by "random" you mean you want the output will be uniformly distributed on the set of all valid arrangements, or in other words, that all valid arrangements are equally likely to be output by the algorithm.

Simple method: rejection sampling

A simple approach is to use rejection sampling: generate a random arrangement, then check if it contains any element $m$ times in a row, and if so throw that away and repeat.

You can generate a random arrangement by starting with the list $[0,1,2,0,1,2,0,1,2,\dots]$ and then applying a random permutation to it, i.e., randomly shuffling it.

This will ensure the output is uniformly distributed. It will be efficient if $m$ is large and inefficient if $m$ is too small. In particular, if $m \ge \log_3 n$, then this should be pretty efficient; the expected number of times you repeat is $O(1)$. On the other hand, if $m \ll \log_3 m$, then this becomes highly inefficient, because you have to repeat many times.

Sophisticated method: ranking/unranking

Here is a more sophisticated technique that will be more efficient if $m$ is small. It works by counting the number of valid arrangements using dynamic programming, and using ranking/unranking techniques.

---

Let's start by looking at how to count the number of valid arrangements. In particular, let $f(n)$ denote the number of valid arrangements of length $n$. I'll show how to compute $f(n)$ using dynamic programming.

To aid with that, let $g(n,x,r,a_1,a_2,a_3)$ denote the number of valid arrangements of length $n$ that use exactly $a_1$ 1's, $a_2$ 2's, $a_3$ 3's, without repeating any number $m$ times in a row, and assuming that before these $n$ you have a sequence of $r$ $x$'s in a row (e.g., if $x=3$ and $r=2$, then a valid sequence is allowed to start with up to $m-r-1$ 3's, but no more than that). Notice that

$$f(n) = g(n-1,1,1,n/3-1,n/3,n/3) + g(n-1,2,1,n/3,n/3-1,n/3) + g(n-1,3,1,n/3,n/3,n/3-1),$$

so if we can compute the $g$'s, we can compute $f$. Also there is a recursive relation among the $g$'s:

$$g(n,1,r,a_1,a_2,a_3) = g(n-1,1,r+1,a_1-1,a_2,a_3) + g(n-1,2,1,a_1,a_2-1,a_3) + g(n-1,3,1,a_1,a_2,a_3-1),$$

which is obtained by a case analysis on the first digit of the sequence, and symmetrically for other values of $x$. (Here I assume we agree on boundary conditions like $g(\cdot,\cdot,m,\cdot,\cdot,\cdot)=0$.)

Now this gives a dynamic programming algorithm for computing $g$, by memoizing, and thus an algorithm for computing $f$. What is the running time? Well, there are at most $3m(n/3)^3 = O(n^3m)$ different subproblems, and solving each one can be done in $O(1)$ time using memoization, so the total running time is $O(n^3m)$.

---

Now that we know how to count, how do we use that to generate a random valid arrangement? We'll use unranking. Since there are $f(n)$ valid arrangements, we can think of each integer in the range $1..f(n)$ as corresponding to a valid arrangement. We will construct an algorithm that can find the arrangement corresponding to a particular integer $i$; then all we need do is pick a random integer in that range, find the corresponding arrangement, and we have a random valid arrangement.

It's easy to use the recursive formula above to build an unranking procedure. Given an integer $i$, we test whether $i \le g(n-1,1,1,n/3-1,n/3,n/3)$; if yes, then the first number in the sequence is 1; if not, we test whether $i \le g(n-1,1,1,n/3-1,n/3,n/3) + g(n-1,2,1,n/3,n/3-1,n/3)$; if yes, then the first number in the sequence is 2, else it is 3. We continue from there to iteratively fill in each element of the sequence.

This lets us pick a valid sequence uniformly at random. The running time is $O(n^3 m)$, so it is efficient for all values of $m$. You can even precompute all of the $g$ values in advance, in which case the running time becomes $O(n)$ per random sequence you want to generate.

Answer 2

I'm pretty sure this would work. The code might not be completely correct because I haven't coded in Python for quite a while.

def generate_sequence(e, n, m):
    r = list(e) * m
    valid = false
    while (!valid):
        random.shuffle(r)
        for i in range(len(r)-n+1):
            if (r[i] == r[i+1] && r[i] == r[i+2] && r[i] == r[i+3]):
                fourInRow = true
                break
        if (!fourInRow) return r