2
$\begingroup$

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]
$\endgroup$
  • $\begingroup$ Why not just cycle through the elements? In your case, you can use 0,1,2,0,1,2,0,1,2,0,1,2. $\endgroup$ – Yuval Filmus Mar 28 '18 at 15:56
  • $\begingroup$ @YuvalFilmus it has to be randomized. The purpose is for different stimuli in a psychological experiment, there should not be a identifiable pattern. That got me thinking about how to do it in an efficient way for any parameters. $\endgroup$ – Adrian Mar 28 '18 at 16:35
  • 1
    $\begingroup$ This requirement should be part of your question. You also have to explain what you mean by "randomized". $\endgroup$ – Yuval Filmus Mar 28 '18 at 17:05
  • $\begingroup$ @YuvalFilmus the question title says randomized list. Guess I forgot that in the first sentence, fixed, thanks. Randomized means random order, not (intentionally) ordered by some criterium. Should be self explanatory. $\endgroup$ – Adrian Mar 28 '18 at 18:47
  • 1
    $\begingroup$ How about randomizing the order of the elements? That is, choose one of 0,1,2,...; 0,2,1,...; 1,0,2,...; 1,2,0,...; 2,0,1,...; 2,1,0,... Is this "randomized"? If not, perhaps you should explain in a little more detail what you mean by randomized. $\endgroup$ – Yuval Filmus Mar 28 '18 at 18:48
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In practice m and m are fairly small for me, so it does not really matter. I am just interested in more sophisticated ways to do something like this after thinking about the problem for a while. As this gets costly with large n. $\endgroup$ – Adrian Mar 28 '18 at 23:10
  • $\begingroup$ @Adrian, OK, I revised my answer to show a more sophisticated method that works for all parameter settings. Hope that's what you were looking for! $\endgroup$ – D.W. Mar 29 '18 at 22:24
0
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ We discourage code-only answers. We are not a coding site. Also, not everyone here reads Python. We're more interested in an explanation of the approach and a justification of why it works. Can you replace or supplement the source code with ideas, pseudo code and arguments of correctness? See here and here for related meta discussions. $\endgroup$ – D.W. Mar 28 '18 at 20:50
  • $\begingroup$ You're just generating random permutations until one works. No need for any code in order to describe this algorithm. $\endgroup$ – Yuval Filmus Mar 28 '18 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.