洗牌有很多重复的列表的有效算法或方法？

Question

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

我需要的是随机排列列表 ['red', 'red', 'red','blue', 'blue'] 的方法，其中单个弹珠的排列无关紧要。

例如 ['red1', 'red2', 'red3','blue', 'blue'] 和 ['red2', 'red1', 'red3','blue', 'blue'] 只有一种解决方案。

因为我的原始问题有更多的一种颜色的弹珠，与其他颜色相比，列表的正常洗牌导致某些顺序的高偏差。

我的一个想法是：

从一个新的空列表开始，
生成 2 个随机整数（第一个整数选择一种颜色，第二个整数决定从该颜色中挑选多少弹珠）
将拾取的弹珠添加到新列表中
重复直到所有弹珠都用完

我想知道是否有更好的方法来解决这个问题，也许可以保证结果的公正性。

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

Answer 1

如果您想要无偏见的洗牌，那么您正在将您的算法与 Knuth 的算法（Fisher-Yate 的略微改进版本）进行比较 shuffle

如果您打算使用两阶段选择进行优化并希望它保持公平，您需要计算获得一、二、三轮相同颜色的概率，并且比相应数量的交换，然后将源中的副本数量复制到目标列表中。

我不会为了性能而费心，因为 1000 个弹珠不太可能通过对交换进行数学运算来提高性能 - 您将不得不在每个阶段进行另一个列表迭代以计算概率，然后进行额外的工作，使其成为 O(N²) 而不是 O(N)。

Answer 2

这将给出独特组合的均匀分布：

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

洗牌有很多重复的列表的有效算法或方法？

Efficient algorithm or method for shuffling a list with many duplicates?

python

algorithm

shuffle

list