Run length control of 2 on a binary variable with python list

user_3921843 0
Viewed 105

I want to pseudo-randomly create a list with 48 entries -- 24 zeros and 24 ones -- where neither zero nor one repeats more than twice in a row. For example:

[1,1,0,1,0,0,1,1,0,1,0,...]

import random
l = list()
for i in range(48):
    if len(l) < 2:
        l.append(random.choice([0,1]))
    else:
        if l[i-1] == l[i-2]:
            if l[i-1] == 0:
                l.append(1)
            else:
                l.append(0)
        else:
            l.append(random.choice([0,1]))

I have the above code, but it sometimes returns an uneven count of 1s or 0s. All possible solutions should have the same chance of coming up.

python-2.7 python
2 Answers

Here is a function that takes an integer n and returns a list that contains n 0s and n 1s.

It obeys the 'no 3 in a row constraint' by first randomly choosing one of the integers 0 or 1 and trying to insert it somewhere in the list by randomly choosing a position and checking whether inserting the integer at that position would violate the constraint. If not, it inserts it there, otherwise it randomly chooses a different position to try. It continues until all n 0s and all n 1s have been put somewhere in the list

It keeps track of how many 0s and 1s have been used so far by decrementing a counter for each after they have been inserted into the list. If there are no more 0s left to add, it will add the rest of the 1s (and vice versa).

The function returns the list once it's length has reached 2*n (all the 0s and 1s have been used up)

import random

def pseudo_rand(n):
    left = {0: n, 1: n} # keep track of how many 1s or 0s you can still use
    out = []
    while len(out) < n*2:
        i = random.randint(0,1) # select 0 or 1 randomly
        if not left[i]: # if have already used up all the 0s or 1s, use the other one instead
            i = 1-i
        possible_pos = list(range(len(out)+1)) # make a list of possible indexes to insert i
        while possible_pos:
            pos = random.choice(possible_pos)
            bottom = max(pos-2, 0)
            top = pos+2
            dz = out[bottom:top] # danger zone: range to inspect to see if we can insert i at position pos  
            if not any(i == dz[j] and i == dz[j-1] for j in range(1, len(dz))): # if inserting i at position pos won't violate the 'no 3 in a row constraint'
                out.insert(pos, i)
                left[i] -= 1
                break
            else: # otherwise don't consider this position anymore
                possible_pos.remove(pos) 
    return out

Some examples:

>>> pseudo_rand(24)
[1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1]

>>> pseudo_rand(5)
[1, 0, 0, 1, 0, 0, 1, 1, 0, 1]
user_59924380

Naive Solution:

import random

def gen_list():
    bin_list=[]
    count=(0,0)
    while len(bin_list)<48:
        choice=random.randint(0,1)
        if choice==0:
            bin_list.append(0)
            count=(count[0]+1,count[1])
        else:
            bin_list.append(1)
            count=(count[0],count[1]+1)
        violates_run_constraint=(len(bin_list)>3) and (bin_list[-1]==bin_list[-2]==bin_list[-3])
        if violates_run_constraint:
            return ([],())
    return (bin_list,count)


bin_list,count=gen_list()
while(bin_list==[] or count!=(24,24)):
    bin_list,count=gen_list()
print(bin_list,count)

gen_list() creates a list of length 48 that only contains 1s and 0s, selected randomly. It also keeps track of how many 1s and 0s it has used and returns this information as a tuple.

However, it can also fail, and violate the constraints. If it does this, it simply returns an empty list.

The outer loop generates lists until it gets a non-constraint-violating list and the number of 1s and the number of 0s in the generated list equals 24.

Probably not the most efficient solution, but definitely works, and a lot faster than I expected.

Example Outputs:

[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1] (24, 24)

[1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0] (24, 24)
user_14562530
Related