python - 包含具有游程长度和频率约束的二进制值的 python 列表的伪随机生成

Question

我想伪随机创建一个包含 48 个条目的列表——24 个零和 24 个一——其中相同的值永远不会连续出现三次。我有以下代码:

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

但是有时候0和1的个数是不均匀的。

Answer 1

在不使用拒绝的情况下获得一致性是很棘手的。

拒绝方法很简单，比如

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

这在 n 很大时会很慢但很可靠。

可能有一种巧妙的方法来获取几乎微不足道的非拒绝样本，但我看不到它，而是转而使用通常有效的方法。如果在每个分支点处，您可以确保对空间进行统一采样，如果您选择该选择，则根据您生成的成功序列的数量对选项进行加权。

因此，我们使用动态规划来制作一个计算可能序列数量的实用程序，并扩展到我们还剩下 (#zeroes, #ones) 位的一般情况，然后使用它来为我们提供权重绘制。 (我们实际上可以将其重构为一个函数，但我认为如果它们是分开的，它们会更清晰，即使它引入了一些重复。)

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

首先，我们可以看到有多少这样的有效序列:

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]

这是A177790在 OEIS，命名为

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

如果您仔细想想，这正是我们所拥有的，将 0 视为东阶，将 1 视为北阶。

我们的随机抽奖看起来不错:

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]

并且非常统一:

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

覆盖也是正确的，因为我们可以通过随机抽样(运气好)来恢复 A177790 计数:

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]