Python 有约束的洗牌

我有一个类似的问题:

我们有20个球，每个球都是唯一的，用一个从1到20的数字来标识.从1到5的球是黄色的，从6到10是绿色的，从10到15是红色的，从16到20是蓝色的.找到一种方法来随机洗牌球，同时遵守约束:"两个连续的球不能有相同的 colored颜色 ".

示例:

我已经考虑了两种我不满意的方法，我正在寻找更好的方法

1. 随机画一个球，然后在所有其他 colored颜色 与前一个不同的球中随机画一个球，以此类推.

问题:在不可能完成绘图的情况下，例如，如果只有相同 colored颜色 的剩余球，我们可能会摔倒.

2. 将球分成4组，每组5个球(每种 colored颜色 1个)，通过随机抽取每种 colored颜色 的一个球，形成另外5组4个球.重新组合这5组以符合标准(最后一组的第一个球被置换，直到符合标准).

问题:有些组合从来不画，例如红、黄、红、黄……绿色，蓝色，绿色，蓝色.

Edit:个

以下是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()}