我正在使用此代码使用 Fisher-Yates 随机化算法的变体生成向量的随机排列(我从第一个元素到最后一个元素,而不是相反)。我在程序启动时boost::random::mt11213b
播种的程序中全局使用RNG generator.seed(time(NULL));
,因此这里有一个包装器单例RandomNumber
。
boost::random::uniform_int_distribution<unsigned long>
distribution(0, vec.size()-1);
for (unsigned long i=0;i<vec.size();i++)
std::swap(vec[i], vec[distribution(RandomNumber::getInstance().generator)]);
简而言之,一些实验让我相信这个算法可能存在问题。这就是我所做的
- 创建了一个长度为 100 的整数向量
- 前 75 个元素填充
0
,后 25 个元素填充1
- 洗牌一个数组。
- 从列表中取出前 5 个元素并将它们相加。
我重复这个过程几千次(循环,而不是手动:))每次都从一个新的向量开始。然后我计算了总和的算术平均值,0.98
而不是预期的1.25
。
1.22
有趣的是,如果我从一个用相同算法而不是有序算法洗牌一次的向量开始,结果会增加结果大约1.25
是预期值。
我不确定可能出了什么问题。该算法看起来不错,我能想到的唯一可能出错的是播种阶段和
boost::random::uniform_int_distribution<unsigned long>
distribution(0, vec.size()-1);
在洗牌向量之前每次调用的行(也许它应该只在程序中调用一次,但这没有意义)
任何帮助将不胜感激!