有约束的随机播放

Question

我有一个类似的问题：

我们有 20 个球，每个球都是唯一的，并通过 1 到 20 的数字进行标识。编号从 1 到 5 的球是黄色，从 6 到 10 是绿色，从 10 到 15 是红色，从 16 到 20 是蓝色。找到一种随机洗球的方法，同时遵守约束：“两个连续的球不能具有相同的颜色”。

例子：

我考虑过两种我不满意的方法，正在寻找更好的一种

1. 随机抽取一个球，然后在所有其他颜色与前一个球不同的球中随机抽取一个球，等等。

问题：我们可能会遇到无法完成绘图的情况，例如，如果仅剩下相同颜色的球。

2. 将球分成 4 组，每组 5 个球（每种颜色 1 个），通过随机抽取每种颜色的球形成另外 5 组，每组 4 个球。重新组装这 5 组以遵守标准（最后一组的第一个球将被排列，直到遵守标准为止）。

问题是有些组合永远不会被绘制，例如红，黄，红，黄......绿，蓝，绿，蓝。

编辑：

这是 Unlikus 解决方案的实现。非常感谢他。

import enum
import random

Color = enum.Enum('Color', ['RED', 'GREEN', 'BLUE', "YELLOW"])

NB_PERMUTATION = {
        (Color.RED, 1, 0, 0, 0): 1,
        (Color.GREEN, 0, 1, 0, 0): 1,
        (Color.BLUE, 0, 0, 1, 0): 1,
        (Color.YELLOW, 0, 0, 0, 1): 1,
        (Color.RED, 0, 0, 0, 0): 0,
        (Color.GREEN, 0, 0, 0, 0): 0,
        (Color.BLUE, 0, 0, 0, 0): 0,
        (Color.YELLOW, 0, 0, 0, 0): 0,
    }

def compute_nb_permutations(*args):
    try:
        return NB_PERMUTATION[args]
    except KeyError:
        second_colors = {1, 2, 3, 4} - {args[0].value}
        nb_ball = [args[1], args[2], args[3], args[4]]
        nb_ball[args[0].value - 1] -= 1
        result = NB_PERMUTATION[args] = sum(
            compute_nb_permutations(Color(c), *nb_ball) for c in second_colors if nb_ball[c - 1] > 0
        )
        return result

def arrange_color():
    colors = {*Color}
    nb_ball = [5,5,5,5]

    # choose uniformly among colors for the first ball
    results = [random.choices(list(colors))[0]]
    nb_ball[results[-1].value - 1] -= 1

    while nb_ball != [0,0,0,0]:
        candidates = list(colors - {results[-1]})
        weights = [compute_nb_permutations(c, *nb_ball) for c in candidates]
        results.append(random.choices(candidates, weights=weights)[0])
        nb_ball[results[-1].value - 1] -= 1

    return results

def draw():
    numbers = {
        Color.RED: list(range(1,6)),
        Color.GREEN: list(range(6, 11)),
        Color.BLUE: list(range(11, 16)),
        Color.YELLOW: list(range(16, 21)),
    }
    for v in numbers.values():
        random.shuffle(v)

    return {numbers[c].pop(): c.name for c in arrange_color()}

Answer 1

在这种规模下，您可以进行拒绝抽样。平均而言，只需不到一百次尝试即可找到有效订单。

import itertools
import random


deck = range(1, 21)


def color(i):
    return "RGBY"[(i - 1) // 5]


shuffle_count = 0


def sample():
    global shuffle_count
    order = list(deck)
    while True:
        shuffle_count += 1
        random.shuffle(order)
        if all(color(i) != color(j) for (i, j) in itertools.pairwise(order)):
            return order


n = 1000
for j in range(n):
    sample()
print(shuffle_count / n)
print(sample())

示例输出：

87.227
[3, 10, 15, 4, 18, 5, 11, 17, 7, 19, 8, 2, 14, 20, 1, 12, 9, 13, 16, 6]

Answer 2

它归结为计算遵守您的约束的排列数。

有关答案，请参阅https://math.stackexchange.com/questions/1208392/ways-to-arrange-4- Different-colour-balls-with-no-two-of-the-same-colour-next-to计算排列球的方式的数量，其中第一个球是一种特定的颜色。（答案涉及最后一个，但数字是相同的）。您可以通过动态规划计算 f 的值。

现在，您按 f(5,5,5,5,red), f(5,5,5,5,green), f(5,5,5,5,blue), f( 5,5,5,5，黄色）。

假设您采样了红色（f 中的第一个颜色）。您按 f(4,5,5,5,green)、f(4,5,5,5,blue)、f(4,5,5,5,yellow) 等比例对第二种颜色进行采样。保证这 3 个值的总和大于 0，因此仍然有解，否则 f(5,5,5,5, red) 已经是 0。

如果颜色正确，数字就很容易了。