Pseudo-random generation of python list containing binary values with run-length and frequency constraints

python generate random list of numbers
python random number generator code
python random list
random number generator python
randint python 3
numpy random number
how to generate random numbers in python without using random
python random sample

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.

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]

9.6. random — Generate pseudo-random numbers, This module implements pseudo-random number generators for various distributions. a function to generate a random permutation of a list in-place, and a function For generating distributions of angles, the von Mises distribution is available. Returns a new list containing elements from the population while leaving the  Source code: Lib/random.py. This module implements pseudo-random number generators for various distributions. For integers, there is uniform selection from a range. For sequences, there is uniform selection of a random element, a function to generate a random permutation of a list in-place, and a function for random sampling without replacement.

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

random — Generate pseudo-random numbers, This module implements pseudo-random number generators for various 623-​dimensionally equidistributed uniform pseudorandom number generator” Returns a new list containing elements from the population while leaving the By re-using a seed value, the same sequence should be reproducible from run to run as  Python provides a random module to generate random numbers. To generate random numbers we have used the random function along with the use of the randint function. randint (start, end) randint accepts two parameters: a starting point and an ending point. Both should be integers and the first value should always be less than the second.

Python Random Module to Generate random Data [Guide], Generate random numbers Choose single and multiple data from Output: Run Online is used to initialize the pseudorandom number generator in Python. Use this function to shuffle or randomize a list or other sequence types. let you know how to generate a random string of a fixed length in python. It involves a pseudo-random number generating technique using binary digits and some simple recursive calculation. It seems like you could do this in your head fairly easily (though a piece of paper would help).

random bit generator: Topics by WorldWideScience.org, Uniqueness: skews bit occurrence frequencies in randomly generated Deterministic algorithms generate pseudo-random numbers at high data on the amount of coding gain obtained by the run-length and Huffman coding, In general, a physical generator contains two parts—a randomness source and its readout. Run Length Encoding in Python; Program to implement Run Length Encoding using Linked Lists; Encoding a word into Pig Latin; Check if an encoding represents a unique binary string; Minimum length of the sub-string whose characters can be used to form a palindrome of length K

[PDF] A statistical test suite for random and pseudorandom , 2.1 Frequency (Monobit) Test. of this paper. Key words: random number generator, hypothesis test, P-value. Abstract-1 detecting deviations of a binary sequence from randomness. However cell contains the number of runs of ones of a given length. The list was compiled based upon NIST statistical testing efforts. 1- Generate all substrings of string1 (“this is a test string”) 2- For each substring, check whether the substring contains all characters of string2 (“tist”) 3- Finally, print the smallest substring containing all characters of string2. Method 2 ( Efficient Solution )

Pseudorandom number generator, A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers  Regular expressions can be used to perform many task in python. To perform this particular task also, regular expressions can come handy. It finds all the matching substring using search () and returns result. # Python code to demonstrate. # to find strings with substrings. # using re + search () # initializing list.

Comments
  • 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: 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
  • Ok. I just ran some tests. You can get runs longer than 2 at the end of the list.
  • I see I will try to fix it.
  • @PM2Ring It's fixed now.