【洗牌算法】C++将数组的元素顺序随机打乱(条件概率证明算法充分随机)

2023-08-04 11:04| 来源: 网络整理| 查看: 265

将数组顺序打乱

做模拟需要用到将一个数组内的元素随机打乱的需求，需要一个‘洗牌算法’，也就是需要生成数组下标的一个随机顺序。

实现的思路如下（思路一比较复杂不好理解，推荐思路二）：

以将一个元素个数为10的数组打乱为例：

思路 1

开始先循环一次生成0-9之间的一个数作为第一个下标，此时原数组的位置已经被占用了一个（实际第一次生成的随机下标就是最终的下标了，因为之前位置没有被占用）；

然后生成一个0-8之间的数作为第二个下标，但这个下标是对应于剩下空间所在的数组的下标，而不是原数组的下标。比如上面第一次生成的下标为6，这里生成的还是6的话，那这里的下标在原数组中应该是7，下标6所在位置已经被占用了。同理如果这里生成的下标是7，那在原数组中对应应为8。但如果这里生成的下标为5，比之前的小，那在原数组中对应下标还是5.问题的难度就在于将生成的下标还原到原数组中，不能出现下标重叠的情况；

之后依次生成0-7，0-6，… ，最后一个确定是0的随机下标。

将得到的10个随机下标还原回原数组中主要是根据随机生成所在的数组和原数组的关系进行下标偏移纠正，这种方法比较绕，下面思路二同样算法的实现比这个简单易理解，程序也更好写。实现代码如下：

/*** 产生随机数组顺序1 ***/ #define LENGTH 25 // 数组长度 #include #include #include using namespace std; // 随机下标数组 int ArrayIndexNew[LENGTH] = {0}; // 随机下标数组原始备份 int ArrayIndex[LENGTH] = {0}; // 恢复完成的原始下标数组 vector DoneArray; // 恢复完成的生成下标数组 vector DoneArrayNew; // 下标偏移纠正量 int offset = 0; /** * 产生一组随机下标 */ void IndexGenerate() { // 生成新的随机下标 for (int i=0; i=0; i--) { offset = 0; for (vector::iterator it = DoneArray.begin(); it != DoneArray.end(); it++) { if (ArrayIndexNew[i] >= *it) { offset++; } } ArrayIndexNew[i] += offset; // 继续恢复相同的下标 do{ offset = 0; for (vector::iterator it = DoneArrayNew.begin(); it != DoneArrayNew.end(); it++) { if (ArrayIndexNew[i] == *it) { offset++; } } ArrayIndexNew[i] += offset; }while (offset); // 当前下标恢复完成 DoneArrayNew.push_back(ArrayIndexNew[i]); DoneArray.push_back(ArrayIndex[i]); } } /** * 打印数组 */ void Print() { cout

【本文地址】

公司简介

联系我们