我有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--;
}
}
关于c# - 如何洗彩球？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7848375/