我正在使用此代码使用 Fisher-Yates 随机化算法的变体生成 vector 的随机排列(我从第一个元素到最后一个元素,而不是相反)。我在一个程序中全局使用 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 的整数 vector
- 用
0
填充前 75 个元素,用1
填充后 25 个元素 - 打乱了一个数组。
- 从列表中取出前 5 个元素并对它们求和。
我重复这个过程几千次(用一个循环,而不是手动 :))每次从一个新的 vector 开始。然后我计算了总和的算术平均值,结果是 0.98
而不是预期的 1.25
。
有趣的是,如果我从一个用相同算法而不是有序算法洗牌过一次的 vector 开始,结果会增加到 1.22
并且如果我不丢弃该 vector 在每次迭代中,而不只是再次洗牌,结果大约是 1.25
,这是预期值。
我不确定哪里出了问题。算法看起来不错,我能想到的唯一可能出错的地方是播种阶段和
boost::random::uniform_int_distribution<unsigned long>
distribution(0, vec.size()-1);
每次在打乱 vector 之前调用的行(也许它应该只在一个程序中调用一次,但这没有意义)
任何帮助将不胜感激!
最佳答案
如果我必须对原因进行猜测,那么您并不是每次都在循环中更改分布大小。 计算机编程艺术算法是here .
一旦你洗牌到 n 个元素,你不想再触及前 n 个,因为重复应用伪随机数不会让事情变得更随机,它们会降低随机性。
关于c++ - 使用 boost::random 改组 vector 时出现问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10286722/