algorithm - 伪随机算法

Question

我想在一个序列上创建一个伪随机算法。 序列看起来像:

A B C D E F A B C D E F A B C D E F A B C D E F...

该算法旨在创建这些字母的较短随机序列，规则是:

• 永远不要有 2 个相同的字母紧随其后(例如 A A B C D)。这个很容易，麻烦接踵而至。
• dyads 只能重复两次(例如 A B A B A C B D 可以，但 A B C D A B A B 不行)；
• tryads 不应该重复(例如 A B C D A B C not ok)。

我不是很擅长算法，而且我已经尝试了很长时间但没有成功，所以我希望你能帮助我!

Answer 1

您可以使用回溯算法，跟踪前两个字符以及到目前为止看到的字符对和三元组的计数。然后递归地生成所有有效序列。为了使其更加随机，您可以对每个递归调用中尝试字符的顺序进行采样/打乱。

如果将其实现为生成器(例如在 Python 中)，则可以使用它生成所有组合，或仅生成下一个此类组合。否则，只返回您找到的第一个解决方案。

Python 示例:

import collections, random
def backtrack(available, n, counts, last=None, lastlast=None):
    if n == 0:
        yield []
    else:
        for c in random.sample(list(available), len(available)):
            # check constraints
            if available[c] == 0: continue
            if c == last: continue
            if last is not None and counts[c+last] > 1: continue
            if lastlast is not None and counts[c+last+lastlast] > 0: continue
            # update counts
            available[c] -= 1
            if last: counts[c+last] += 1
            if lastlast: counts[c+last+lastlast] += 1
            # recursive call to get remainder
            for rest in backtrack(available, n-1, counts, c, last):
                yield [c] + rest
            # reset counts
            available[c] += 1
            if last: counts[c+last] -= 1
            if lastlast: counts[c+last+lastlast] -= 1

例子:

lst = "A B C D E F A B C D E F A B C D E F A B C D E F".split()
print(next(backtrack(collections.Counter(lst), 6, collections.Counter())))
print(next(backtrack(collections.Counter(lst), 6, collections.Counter())))
print(next(backtrack(collections.Counter(lst), 6, collections.Counter())))
res = list(backtrack(collections.Counter(lst), 6, collections.Counter()))
print(len(res))

输出:

['A', 'C', 'B', 'A', 'E', 'A']
['A', 'F', 'A', 'E', 'D', 'A']
['E', 'D', 'E', 'F', 'E', 'B']
18360

但是，根据您的列表和要从中获取的元素数量，也可能只从列表中生成随机样本并检查约束，直到找到一个可行的样本。