迭代随机排列的算法

Question

我有一个包，里面有:

• 6 个红色弹珠
• 5 个绿色弹珠
• 2个蓝色弹珠

我想从袋子里随机取出一颗弹珠，记录它的颜色，然后重复直到袋子里没有弹珠为止:

1. 对计数进行排序
   • bag = {2:blue, 5:green, 6:red}
2. 计算累计计数
   • 累积 = {2:blue, 7:green, 13:red}
3. 在[0, max cumulative count]中选择一个随机数
   • rand(0, 13) = 3
4. 使用二进制搜索找到这个整数的插入点索引
   • 我=1
5. 记录这个索引对应的颜色
   • 绿色
6. 将计数减 1
   • bag = {2:blue, 4:green, 6:red}
7. 重复直到袋子里没有弹珠

这是执行此操作的好方法还是在时间复杂度方面有更有效的方法？

Answer 1

你的算法很不错，但还可以进一步优化:

1. 您不需要对颜色进行排序!您可以跳过第一步。

2. 不必每次都计算累积计数，您可以通过减少所选颜色右侧的所有值(包括所选颜色本身)来迭代执行此操作。

3. 您也不需要二分查找，您可以从末尾开始减少累积计数，直到达到正确的数字。

还有一种基于列表的算法:

1. 创建一个包含所有项目的列表(0=红色，1=绿色，2=蓝色):[0,0,0,0,0,0,1,1,1,1,1, 2,2].

2. 获取介于 0 和列表大小 - 1 之间的随机整数 i。

3. 从列表中删除第 i 项并将其添加到结果中。

4. 重复 2. 和 3. 直到列表为空。