如何洗牌彩球

本文关键字：何洗牌 | 更新日期: 2023-09-27 18:12:12

我有400个球，其中100个是红色的，40个是黄色的，50个是绿色的，60个是蓝色的，70个是紫色的，80个是黑色的。(相同颜色的球是相同的)

我需要一个高效的洗牌算法，使洗牌后的球在一个列表中，并且

连续的3个球颜色不相同。例如，我不能有"红色，红色，红色，黄色...."

并且，所有排列都是"等"可能发生的。(好吧，如果效率和公正之间的权衡足够好，我不介意效率比公正更高)。

我试图改编Fisher-Yates-Knuth，但结果并不理想。

为什么Fisher-Yates不够好?由于FY采用蒙特卡罗逆变换。输出分布以不同的方式对待相同的颜色球，也就是说，它会根据我的需求产生有偏差的结果。

并且，天真的想法是过滤掉/回溯整个空间中所有糟糕的排列。当限制非常强时，例如，如果我们只有300个球，其中100个是红色的，那么在获得适当的排列之前会有太多的回溯/失败。

所以，最终，我希望能够遍历所有好的排列。然而，由于有效排列的数量太大，我只能随机抽样其中的一些。

如何洗牌彩球

据我所知，FYK算法是在数组中交换随机位置。为什么你不能产生我在伪代码中描述的颜色呢?

public IEnumerable<Color> GetColors()
{
   int count = 400;
   // queue or another data structure to hold the last generated colors
   Queue<Color> lastColors = new Queue<Color>(); 
   var availableColor = new Dictionary<Color, int> { 
     {Red, 100}, {Yellow, 40}, ...
   };
   Color nextColor = null;
   while(count > 0)
   {
     do {
       /* randomly pick from color buckets */
       nextColor = /* choose random color based on the weights*/;
     } while(/*it satisfies the condition, that it is not 3rd same color in a row*/)
     yield return nextColor;
     count--;
   }
}

自言自语，我想试试

  • "设计"(考虑)有效组合的(递归)生成器;确保它以确定的顺序生成组合;
  • 将生成器转换为确定的编号方案(一个唯一标识任何一个有效组合的神奇数字)2
  • 实现以目标幻数作为参数的生成器算法，这样你就不必做所有的工作来获得'n个有效组合'，而是可以'跳转'到所需的组合(这要求你的递归生成函数显式和确定性;任何回溯都将使这成为不可能)。

现在，您可以简单地在[0.. max_number_of_valid_组合]1之间生成均匀分布的随机"魔术"数。对于每个选定的幻数，您可以打印生成的有效组合。

如果你感兴趣，我可能会找时间试一试。(我更喜欢在c++/Python中这样做，但c#应该是可能的(.Net 4.0是否已经发布了BigInteger类?))

1(这可能是一个巨大的数字，所以您可能会被某种BigInteger所迷惑，并生成多个随机数来得到大数。确保你理解了分布算法，以确保它仍然是均匀分布的…

2有大量的组合来达到适当的乘数，以找到在生成过程中特定点可能的"尾部组合"的数量。这就是复杂性瓶颈IMO

相关文章：