algorithm - 生成半随机序列的有效方法

Question

很多时候，我必须以某种半随机的方式生成数字序列，这意味着它不是完​​全随机的，而是必须具有一些其他属性。例如，我们需要 1、2、3 和 4 的随机序列，但任何数字都必须连续重复三次。这些通常做起来不是很复杂，但我遇到了一个棘手的问题:我需要生成一个长度超过 400 的半随机序列，由 1,2,3 和 4 组成，每个数字必须出现相同次数(或者如果总和不能被四整除而不是尽可能接近)并且它们不能连续重复 3 次(所以 1,3,4,4,4,2 不行) .

我尝试了方法:

1. 创建一个具有所需长度和数字数量的列表；洗牌；检查连续数字是否可以，如果不可以，请重新洗牌。

2. 创建一个具有所需长度和数字数量的列表；生成所有排列并选择合适的排列；保存这些以备后用，并在需要时随机选择其中之一。

第一个方法运行了几分钟，然后产生任何正确的序列，第二个方法生成了太多的排列，我的 jupter notebook 放弃了。

这是第一个的python代码

from random import shuffle

v = []
for x in range(108):
    v += [1,2,3,4]
shouldicontinue = 1
while shouldicontinue:
    shuffle(v)
    shouldicontinue = 0
    for h in range(len(v)-1):
        if v[h] == v[h+1] and v[h] == v[h+2]:

            shouldicontinue = 1
            break
        else:
            pass

第二个

from random import shuffle
import itertools
v = []
for x in range(108):
    v += [1,2,3,4]
good = []
for l in itertools.permutations(v):
    notok = 0
    for h in range(len(v)-1):
        if v[h] == v[h+1] and v[h] == v[h+2]:

            notok = 1
            break
        else:
            pass
    if not notok:
        good.append(v)

我正在寻找一种有效解决此问题的方法，即:如果它实时运行，则在速度较慢的计算机上生成所需的时间不超过一分钟，或者如果它是提前准备好的在某种程度上(如方法 2 的想法)，它可以在几小时内在一些中等水平的计算机上准备好。

Answer 1

在您可以检查 >400 长度列表的所有排列之前，宇宙可能已经死亡。因此，您需要另一种方法。

在这里，我建议尝试随机插入列表中的元素，但当插入会破坏其中一个要求时转移到下一个索引。

循环遍历您的元素，在您的情况下，1 到 4 应确保始终可以插入。

from itertools import cycle, islice
from random import randint

def has_repeated(target, n, lst):
    """A helper to check if insertion would break the max repetition requirement"""
    count = 0
    for el in lst:
        count += el == target
        if count == n:
            return True
    return False

def sequence(length, max_repeat, elements=(1, 2, 3, 4)):
    # Iterator that will yield our elements in cycle
    values = islice(cycle(elements), length)

    seq = []
    for value in values:
        # Pick an insertion index at random
        init_index = randint(0, len(seq))

        # Loop over indices from that index until a legal position is found
        for shift in range(len(seq) + 1):
            index = init_index - shift
            slice_around_index = seq[max(0, index - max_repeat):index + max_repeat]

            # If the insertion would cause no forbidden subsequence, insert
            if not has_repeated(value, max_repeat, slice_around_index):
                seq.insert(index, value)
                break

        # This will likely never happen, except if a solution truly does not exist
        else:
            raise ValueError('failed to generate the sequence')
    return seq

示例

这里是一些示例输出，用于检查结果是否正确。

for _ in range(10):
    print(sequence(25, 2))

输出

[4, 1, 4, 1, 3, 2, 1, 2, 4, 1, 4, 2, 1, 2, 2, 4, 3, 3, 1, 4, 3, 1, 2, 3, 3]
[3, 1, 3, 2, 2, 4, 1, 2, 2, 4, 3, 4, 1, 3, 4, 3, 2, 4, 4, 1, 1, 2, 1, 1, 3]
[1, 3, 2, 4, 1, 3, 4, 4, 3, 2, 4, 1, 1, 3, 1, 2, 4, 2, 3, 1, 1, 2, 4, 3, 2]
[1, 3, 2, 4, 1, 2, 2, 1, 2, 3, 4, 3, 2, 4, 2, 4, 1, 1, 3, 1, 3, 4, 1, 4, 3]
[4, 1, 4, 4, 1, 1, 3, 1, 2, 2, 3, 2, 4, 2, 2, 3, 1, 3, 4, 3, 2, 1, 3, 1, 4]
[2, 3, 3, 1, 3, 3, 1, 2, 1, 2, 1, 2, 3, 4, 4, 1, 3, 4, 4, 2, 1, 1, 4, 4, 2]
[3, 2, 1, 4, 3, 2, 3, 1, 4, 1, 1, 2, 3, 3, 2, 2, 4, 1, 1, 2, 4, 1, 4, 3, 4]
[4, 4, 3, 1, 4, 1, 2, 2, 4, 4, 3, 2, 2, 3, 3, 1, 1, 2, 1, 1, 4, 1, 2, 3, 3]
[1, 4, 1, 4, 4, 2, 4, 1, 1, 2, 1, 2, 2, 3, 3, 2, 2, 3, 1, 4, 4, 3, 3, 1, 3]
[4, 3, 2, 1, 4, 1, 1, 2, 2, 3, 3, 1, 4, 4, 1, 3, 2, 3, 4, 2, 1, 1, 4, 2, 3]

在效率方面，在相同要求下生成长度为 10,000 的列表大约需要 10 毫秒。暗示这对于大多数目的来说可能是一个足够有效的解决方案。