4

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.

jtm_beta
  • 145
  • 8
  • What do you mean by `consecutively` in this case? At the moment, you would only get 8 unique combinations so if you wanted a length of 48 you'd have 6 repeats for each combination. – Woody1193 Sep 21 '18 at 18:17
  • By consecutively I mean that the value of any variable should not repeat more than twice in a row. So you could never get three consecutive sublists with "forward" – jtm_beta Sep 21 '18 at 18:27
  • 48 is the number of sublists. 24 is the number of times each unique value occurs across all of the lists – jtm_beta Sep 21 '18 at 18:32
  • 3
    @cricket_007 I would agree that the original question was a dup but his new edited version has original elements, suggested by his use of the term "pseudo-randomly". – Woody1193 Sep 21 '18 at 18:55
  • 2
    I'm not sure that the question as phrased (since the edit) is a duplicate of that marked. – code11 Sep 21 '18 at 18:56
  • 1
    Why is it marked as dupe? – mad_ Sep 21 '18 at 19:05
  • @mad_ Look at the initial question – OneCricketeer Sep 21 '18 at 19:43
  • Regarding what is being asked now... Are you having difficulties tracking the previous two values that are added to a list? If you generate `0/1`, then you can easily know if you have a previous consecutive numbers – OneCricketeer Sep 21 '18 at 19:47
  • The difficulty is not tracking the previous two values, but ensuring that there are 24 of each by the time we reach 48 – jtm_beta Sep 21 '18 at 19:59
  • What if you kept a counter of how many of each you have used, randomly select a `0` or `1` if you haven't used up all 24, randomly choose an position in your output list, check if you can insert your value in that position without violating your 3 in a row constraint. Then repeat until everything is inserted. – bunji Sep 21 '18 at 20:26
  • If you don't think this should have been marked as a duplicate please reformulate the question and ask it again. As it stands, the question is closed and so we can't actually answer it. – bunji Sep 21 '18 at 21:06
  • Do you require uniformity over the entire space of such sequences? – DSM Sep 21 '18 at 21:28
  • No. I just require a list containing 24 zeros and 24 ones, where the same value never occurs three times in a row. – jtm_beta Sep 21 '18 at 21:36
  • @jtm_beta that moves it away from random – khachik Sep 21 '18 at 21:38
  • Then I misinterpreted what was meant by "uniformity over the entire space of such sequences". It needs to be pseudo-random, so random as far the constraints will allow – jtm_beta Sep 21 '18 at 21:44
  • 1
    @jtm_beta: what I meant was that there's a finite number of such sequences, say N. Do you need each one to have a 1/N chance of coming up? Or if it were a die, would you be okay with 1,2,4 coming up more frequently than 3,5 and 6 never coming up at all? – DSM Sep 22 '18 at 01:51
  • 1
    @DSM: each possible solution should have a 1/N chance of coming up – jtm_beta Sep 22 '18 at 06:42

2 Answers2

1

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]
bunji
  • 5,063
  • 1
  • 17
  • 36
1

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)
code11
  • 1,986
  • 5
  • 29
  • 37