对包含多个重复项的列表进行洗牌的有效算法或方法？

Question

假设我有5个弹珠，3个是红色的，2个是蓝色的。 相同颜色的大理石从1到n编号，其中n是该颜色大理石的数量

我需要的是对列表进行洗牌，其中单个大理石的排列并不重要

例如 ['red1', 'red2', 'red3','blue', 'blue']和 ['red2', 'red1', 'red3','blue', 'blue'] 只有一种解决办法

因为我最初的问题是一种颜色的大理石比其他颜色的大理石多得多，所以列表的正常无序排列会导致某些顺序的高偏差

我的一个想法是：

1. 从一个新的空列表开始
2. 生成2个随机整数（第一个整数用于选择颜色，第二个整数用于确定要拾取该颜色的大理石数量）
3. 将拾取的大理石附加到新列表中
4. 重复上述步骤，直到所有弹珠都用完为止

我想知道是否有更好的方法来解决这个问题，也许有更可靠的无偏结果

编辑： 一个小规模的场景是4种不同的颜色，每种颜色有2到5个大理石。 一个现实的场景是20种不同的颜色，每种颜色有5到50颗大理石

Answer 1

这将使Unique组合的分布均匀：

from random import randrange
from collections import Counter
def marblePick(marbles):
    remaining = list(Counter(marbles).elements())
    return [remaining.pop(randrange(r)) for r in range(len(remaining),0,-1)]

性能似乎是线性的，我通过如下抽样测试了分布：

marbles = {"R":3,"B":2}

N = 1000000
dist = Counter()
for _ in range(N):
    combo = marblePick(marbles)
    dist[tuple(combo)]+=1

for s,c in dist.items():
    print(s,c/N)

import statistics as stats
prop = [c/N for c in dist.values()]
mean = stats.mean(prop)
stdev = stats.stdev(prop)
print("mean:",mean,"stdDev:",f"{100*stdev/mean:.1f}%",N,"samples",len(dist),"combos")

该样本（以及我尝试过的其他几个样本）的结果具有决定性：

('B', 'R', 'B', 'R', 'R') 0.100245
('R', 'R', 'R', 'B', 'B') 0.099789
('R', 'R', 'B', 'B', 'R') 0.099952
('B', 'R', 'R', 'B', 'R') 0.100579
('R', 'R', 'B', 'R', 'B') 0.099732
('R', 'B', 'R', 'R', 'B') 0.100033
('B', 'B', 'R', 'R', 'R') 0.099861
('B', 'R', 'R', 'R', 'B') 0.099941
('R', 'B', 'R', 'B', 'R') 0.100103
('R', 'B', 'B', 'R', 'R') 0.099765
mean: 0.1 stdDev: 0.3% 1000000 samples 10 combos

Answer 2

如果你想要一个无偏的洗牌，那么你将把你的算法与Knuth的（Fisher-Yate的稍有改进的版本）shuffle

如果您打算使用两阶段选择进行优化，并希望其保持公平，则需要计算获得相同颜色的一、二、三个运行的概率，并比相应的交换数量更有效地执行此计算，然后将源中的副本数量写入目标列表

为了性能，我不想费心了，因为对于1000颗弹珠，你不太可能通过在交换过程中进行数学运算来提高性能——你必须在每个阶段进行另一次列表迭代来计算概率，然后进行额外的工作，这将使它成为O（N²）而不是O（N）