随机置换迭代算法

Question

我有一个包，有以下内容：

• 6颗红色大理石

我想从袋子里取出一个随机的弹珠，记录它的颜色，然后重复，直到袋子里不再剩下弹珠：

• 排序计数
  • 包={2：蓝色，5：绿色，6：红色}
  • 累计={2：蓝色，7：绿色，13：红色}
  • 兰德（0,13）=3
  • i=1
  • 绿色的
  • 袋子={2:蓝色，4:绿色，6:红色}

  这是一种很好的方法，还是在时间复杂度方面有更有效的方法？

Answer 1

您可以就地打乱数组，而不是依赖于提取。

>

就像在马拉卡的回答中一样，您将项目单独存储在数组中（这里引用它：“创建一个包含所有项目的列表（0=红色，1=绿色，2=蓝色）：[0,0,0,0,0,0,0,1,1,1,1,1,2]。）

遍历数组，为每个元素i，选择要交换位置的元素的随机索引j

最后，只需在数组上迭代即可得到一个无序顺序。

差不多

for(i=0..len-1) {
  j=random(0..len-1);
  // swap them
  aux=a[i]; a[i]=a[j]; a[j]=aux;
}
// now consume the array - it is as random as it can be
// without extracting from it on the way

注意：许多编程语言将有库提供已经实现的数组/列表洗牌功能

>

Java-集合。洗牌

Python——随机。洗牌

Answer 2

你的算法很好，但可以进一步优化：

>

你不需要对颜色进行排序！你可以跳过第一步。

与每次计算累积计数不同，您可以通过减少选定颜色（包括选定颜色本身）右侧的所有值来迭代计算累积计数。

您也不需要进行二进制搜索，只需从末尾开始减少累积计数，直到达到正确的数字。

还有另一种基于列表的算法：

>

创建包含所有项目（0=红色，1=绿色，2=蓝色）的列表：[0,0,0,0,0,0,1,1,1,1,1,2,2]。

获取一个介于0和list-1大小之间的随机整数i。

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

重复2次。三,。直到列表为空。