2

I want to pseudo-randomly create a list with 48 entries -- 24 zeros and 24 ones -- where the same value never occurs three times in a row. I have the following code:

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]))

But sometimes the count of 0s and 1s is uneven.

2
  • You aren't keeping track of the number of zeroes or ones, so it's entirely possible that you won't have an equal number of each at the end.
    – jfowkes
    Sep 21, 2018 at 21:57
  • @jfowkes: That's true. The only condition is that there are no 0 0 0 or 1 1 1. This means for example, 0 0 1 1 0 0 and 0 1 0 0 1 0, both fulfill this condition but in the first case you have three 0 three 1 but in the second case you have four 0 and two 1. Same logic can be applied to 48 entries
    – Sheldore
    Sep 21, 2018 at 22:04

3 Answers 3

3

Getting uniformity without using rejection is tricky.

The rejection approach is straightforward, something like

def brute(n):
    seq = [0]*n+[1]*n
    while True:
        random.shuffle(seq)
        if not any(len(set(seq[i:i+3])) == 1 for i in range(len(seq)-2)):
            break
    return seq

which will be very slow at large n but is reliable.

There's probably a slick way to take a non-rejection sample where it's almost trivial, but I couldn't see it and instead I fell back on methods which work generally. You can make sure that you're uniformly sampling the space if at each branch point, you weight the options by the number of successful sequences you generate if you take that choice.

So, we use dynamic programming to make a utility which counts the number of possible sequences, and extend to the general case where we have (#zeroes, #ones) bits left, and then use this to provide the weights for our draws. (We could actually refactor this into one function but I think they're clearer if they're separate, even if it introduces some duplication.)

from functools import lru_cache
import random

def take_one(bits_left, last_bits, choice):
    # Convenience function to subtract a bit from the bits_left
    # bit count and shift the last bits seen.
    bits_left = list(bits_left)
    bits_left[choice] -= 1
    return tuple(bits_left), (last_bits + (choice,))[-2:]


@lru_cache(None)
def count_seq(bits_left, last_bits=()):
    if bits_left == (0, 0):
        return 1  # hooray, we made a valid sequence!
    if min(bits_left) < 0:
        return 0  # silly input
    if 0 in bits_left and max(bits_left) > 2:
        return 0  # short-circuit if we know it won't work
    tot = 0
    for choice in [0, 1]:
        if list(last_bits).count(choice) == 2:
            continue  # can't have 3 consec.
        new_bits_left, new_last_bits = take_one(bits_left, last_bits, choice)
        tot += count_seq(new_bits_left, new_last_bits)
    return tot

def draw_bits(n):
    bits_left = [n, n]
    bits_drawn = []
    for bit in range(2*n):
        weights = []
        for choice in [0, 1]:
            if bits_drawn[-2:].count(choice) == 2:
                weights.append(0)  # forbid this case
                continue

            new_bits_left, new_last_bits = take_one(bits_left, tuple(bits_drawn[-2:]), choice)
            weights.append(count_seq(new_bits_left, new_last_bits))

        bit_drawn = random.choices([0, 1], weights=weights)[0]
        bits_left[bit_drawn] -= 1
        bits_drawn.append(bit_drawn)
    return bits_drawn

First, we can see how many such valid sequences there are:

In [1130]: [count_seq((i,i)) for i in range(12)]
Out[1130]: [1, 2, 6, 14, 34, 84, 208, 518, 1296, 3254, 8196, 20700]

which is A177790 at the OEIS, named

Number of paths from (0,0) to (n,n) avoiding 3 or more consecutive east steps and 3 or more consecutive north steps.

which if you think about it is exactly what we have, treating a 0 as an east step and a 1 as a north step.

Our random draws look good:

In [1145]: draw_bits(4)
Out[1145]: [0, 1, 1, 0, 1, 0, 0, 1]

In [1146]: draw_bits(10)
Out[1146]: [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0]

and are quite uniform:

In [1151]: Counter(tuple(draw_bits(4)) for i in range(10**6))
Out[1151]: 
Counter({(0, 0, 1, 0, 1, 0, 1, 1): 29219,
         (1, 0, 1, 0, 0, 1, 0, 1): 29287,
         (1, 1, 0, 0, 1, 0, 1, 0): 29311,
         (1, 0, 1, 0, 1, 0, 1, 0): 29371,
         (1, 0, 1, 0, 1, 1, 0, 0): 29279,
         (0, 1, 0, 1, 0, 0, 1, 1): 29232,
         (0, 1, 0, 1, 1, 0, 1, 0): 29824,
         (0, 1, 1, 0, 0, 1, 1, 0): 29165,
         (0, 1, 1, 0, 1, 0, 0, 1): 29467,
         (1, 1, 0, 0, 1, 1, 0, 0): 29454,
         (1, 0, 1, 1, 0, 0, 1, 0): 29338,
         (0, 0, 1, 1, 0, 0, 1, 1): 29486,
         (0, 1, 1, 0, 1, 1, 0, 0): 29592,
         (0, 0, 1, 1, 0, 1, 0, 1): 29716,
         (1, 1, 0, 1, 0, 0, 1, 0): 29500,
         (1, 0, 0, 1, 0, 1, 0, 1): 29396,
         (1, 0, 1, 0, 0, 1, 1, 0): 29390,
         (0, 1, 1, 0, 0, 1, 0, 1): 29394,
         (0, 1, 1, 0, 1, 0, 1, 0): 29213,
         (0, 1, 0, 0, 1, 0, 1, 1): 29139,
         (0, 1, 0, 1, 0, 1, 1, 0): 29413,
         (1, 0, 0, 1, 0, 1, 1, 0): 29502,
         (0, 1, 0, 1, 0, 1, 0, 1): 29750,
         (0, 1, 0, 0, 1, 1, 0, 1): 29097,
         (0, 0, 1, 1, 0, 1, 1, 0): 29377,
         (1, 1, 0, 0, 1, 0, 0, 1): 29480,
         (1, 1, 0, 1, 0, 1, 0, 0): 29533,
         (1, 0, 0, 1, 0, 0, 1, 1): 29500,
         (0, 1, 0, 1, 1, 0, 0, 1): 29528,
         (1, 0, 1, 0, 1, 0, 0, 1): 29511,
         (1, 0, 0, 1, 1, 0, 0, 1): 29599,
         (1, 0, 1, 1, 0, 1, 0, 0): 29167,
         (1, 0, 0, 1, 1, 0, 1, 0): 29594,
         (0, 0, 1, 0, 1, 1, 0, 1): 29176})

Coverage is also correct, in that we can recover the A177790 counts by randomly sampling (and with some luck):

In [1164]: [len(set(tuple(draw_bits(i)) for _ in range(20000))) for i in range(9)]
Out[1164]: [1, 2, 6, 14, 34, 84, 208, 518, 1296]
2

Here's a reasonably efficient solution that gives you fairly random output that obeys the constraints, although it doesn't cover the full solution space.

We can ensure that the number of zeroes and ones are equal by ensuring that the number of single zeros equals the number of single ones, and the number of pairs of zeros equals the number of pairs of ones. In a perfectly random output list we'd expect the number of singles to be roughly double the number of pairs. This algorithm makes that exact: each list has 12 singles of each type, and 6 pairs.

Those run lengths are stored in a list named runlengths. On each round, we shuffle that list to get the sequence of run lengths for the zeros, and shuffle it again to get the sequence of run lengths for the ones. We then fill the output list by alternating between runs of zeroes and ones.

To check that the lists are correct we use the sum function. If there are equal numbers of zeroes and ones the sum of a list is 24.

from random import seed, shuffle

seed(42)

runlengths = [1] * 12 + [2] * 6
bits = [[0], [1]]
for i in range(10):
    shuffle(runlengths)
    a = runlengths[:]
    shuffle(runlengths)
    b = runlengths[:]
    shuffle(bits)
    out = []
    for u, v in zip(a, b):
        out.extend(bits[0] * u)
        out.extend(bits[1] * v)
    print(i, ':', *out, ':', sum(out))

output

0 : 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 : 24
1 : 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 : 24
2 : 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 : 24
3 : 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 : 24
4 : 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 0 : 24
5 : 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 : 24
6 : 1 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 : 24
7 : 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 0 1 : 24
8 : 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 : 24
9 : 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 : 24
1

Here is a simple code that obeys your constraints:

import random


def run():
    counts = [24, 24]
    last = [random.choice([0, 1]), random.choice([0, 1])]
    counts[last[0]] -= 1
    counts[last[1]] -= 1

    while sum(counts) > 0:
        can_pick_ones = sum(last[-2:]) < 2 and counts[1] > 0.33 * (48 - len(last))
        can_pick_zeros = sum(last[-2:]) > 0 and counts[0] > 0.33 * (48 - len(last))

        if can_pick_ones and can_pick_zeros:
            value = random.choice([0, 1])
        elif can_pick_ones:
            value = 1
        elif can_pick_zeros:
            value = 0

        counts[value] -= 1
        last.append(value)
    return last


for i in range(4):
    r = run()
    print(sum(r), r)

Output

24 [1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0]
24 [0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1]
24 [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1]
24 [1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0]

Rationale

At each step of the while loop you can either choose 1, choose 0 or both. You can choose:

  • 1 if the last two elements are not one and the counts of 1 is larger than 1/3 the amount of remaining slots: sum(last[-2:]) < 2 and counts[1] > 0.33 * (48 - len(last))
  • 0 if the last two elements are not 0 and the counts of 0 is larger than 1/3 the amount of remaining slots: sum(last[-2:]) > 0 and counts[0] > 0.33 * (48 - len(last))
  • Both if you can choose 1 or 0

The sum of the two last elements can be 0, 1 or 2, if equals 0 it means that the last two elements were 0 so you can only pick 0 if sum(last[-2:]) > 0. If equals 2 it means that the last two elements where 1, so you can only pick 1 if sum(last[-2:]) < 2. Finally you need to check that the amount of elements of both 1 and 0 are at least a third of the remaining positions to assign, otherwise you are going to be forced to create a run of three consecutive equal elements.

3
  • Ok. I just ran some tests. You can get runs longer than 2 at the end of the list.
    – PM 2Ring
    Sep 21, 2018 at 23:06
  • I see I will try to fix it. Sep 21, 2018 at 23:07
  • @PM2Ring It's fixed now. Sep 22, 2018 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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