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]