带约束的随机洗牌问题求解：相邻球颜色不得相同

数据老陈

2026-7-21

问题

现有20个带唯一编号的球：编号1-5为黄色，6-10为绿色，11-15为红色，16-20为蓝色。需要设计一种随机洗牌方法，满足约束：相邻两个球颜色不能相同。

尝试过两种方法，但均存在缺陷：

方法1：随机抽取第一个球，之后每次从剩余的不同颜色球中随机抽取。
问题：可能出现无法完成抽取的情况，例如剩余球均为同一颜色时，无法继续满足相邻颜色不同的约束。
方法2：将球按颜色分为4组（每组5个），从每组随机取一个球组成5个新组，再重组这些组以满足约束（调整最后一组的首个球直至符合要求）。
问题：某些合法的序列永远无法生成，例如「红、黄、红、黄……」「绿、蓝、绿、蓝……」这类交替序列。

解决方案

编辑补充：以下是Unlikus提供的解决方案实现代码，核心思路是通过计算合法排列数加权随机选择，确保所有合法序列都能被等概率生成，同时避免中途卡壳的问题。

import enum
import random

# 定义颜色枚举
Color = enum.Enum('Color', ['RED', 'GREEN', 'BLUE', "YELLOW"])

# 缓存已计算的合法排列数，避免重复计算
NB_PERMUTATION = {
    # 基础情况：只剩1个某颜色球时，仅1种排列方式
    (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,
    # 无剩余球时，排列数为0
    (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(last_color, red_count, green_count, blue_count, yellow_count):
    """计算以last_color结尾、剩余各颜色球数量为指定值时的合法排列数"""
    try:
        # 优先查询缓存，减少计算量
        return NB_PERMUTATION[(last_color, red_count, green_count, blue_count, yellow_count)]
    except KeyError:
        # 可选颜色为上一个颜色之外的所有颜色
        available_color_values = {1, 2, 3, 4} - {last_color.value}
        # 复制当前剩余球数量，模拟选择后的状态
        remaining = [red_count, green_count, blue_count, yellow_count]
        # 减去已使用的最后一个颜色的球
        remaining[last_color.value - 1] -= 1
        
        # 递归求和所有可选颜色对应的合法排列数
        total = sum(
            compute_nb_permutations(Color(c), *remaining) 
            for c in available_color_values 
            if remaining[c - 1] > 0
        )
        # 将计算结果存入缓存
        NB_PERMUTATION[(last_color, red_count, green_count, blue_count, yellow_count)] = total
        return total

def arrange_color():
    """生成符合相邻颜色不同约束的随机颜色序列"""
    all_colors = set(Color)
    # 初始各颜色球数量均为5
    remaining_counts = [5, 5, 5, 5]
    
    # 第一个颜色随机均匀选择
    color_sequence = [random.choice(list(all_colors))]
    remaining_counts[color_sequence[-1].value - 1] -= 1
    
    # 循环直到所有球都被选中
    while remaining_counts != [0, 0, 0, 0]:
        # 可选颜色排除上一个颜色
        candidates = list(all_colors - {color_sequence[-1]})
        # 计算每个候选颜色对应的合法后续排列数，作为随机选择的权重
        weights = [compute_nb_permutations(c, *remaining_counts) for c in candidates]
        # 按权重随机选择下一个颜色
        next_color = random.choices(candidates, weights=weights)[0]
        color_sequence.append(next_color)
        # 更新剩余球数量
        remaining_counts[next_color.value - 1] -= 1
    
    return color_sequence

def draw():
    """生成带编号的最终洗牌结果"""
    # 初始化各颜色对应的编号列表
    number_pool = {
        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 nums in number_pool.values():
        random.shuffle(nums)
    
    # 根据颜色序列生成编号-颜色映射
    return {number_pool[c].pop(): c.name for c in arrange_color()}

内容的提问来源于stack exchange，提问作者René paul Debroize