c++ - 关于非重复 rand 函数

Question

我尝试生成 25 个数组，每个数组应包含数字 1 到 25，且无重复且无序。我执行生成数组的代码，没有重复。当我试图将数组映射到二维数组时，数组中有重复的数字。

这是我的代码

int permutation(int arraystore[]){

int item[25], index;
for (int x = 0; x < 25; x++)
    item[x] = x;                  //input values into item array

for (int x = 25; x > 0; x--) {
    index = rand() % x;     //generate random numbers
    arraystore[x] = item[index];
    while (index < x - 1) {             
        item[index] = item[index + 1];
        index++;
        }
    }
}

我将 arraystore 映射到 main 中的二维数组

int main(){
int ddarray[25][25];
for(int j=0;j<25)
    for(int i=0;i<25;i++){
        int array[25];
        permutation(array);
        ddarray[j][i]=array[i];
    }
}

部分结果

192,9,7,3,11,20,18,9,23,< strong>11,21,5,11,17,5,12,11,3,10,9,2 ,5,7,7,19, 192,5,0,14,23,22,6,2,20,24,13,12,21,24,21,6,11,21,1,20,5,8, 6,12,15, 192,21,6,14,14,11,11,8 ,17,19,9,24,22,6,24,11>,2,22,6,13,2,18,6,14,20,

我是不是在置换函数中做错了什么或遗漏了什么？

感谢您回答我的问题!

Answer 1

这里有几处可以/必须改进的地方。

• 首先，我建议使用 std::shuffle而不是推出自己的版本。

• 使您的程序非法 C++ 的主要问题:如果 x 是 25，那么您尝试写入 arraystore[x]，这是一个 25 元素数组的末尾。您可能想要写入 arraystore[x-1]。

• 给您重复输出的主要问题:您正在为内部循环中的每个 i 随机化一个新数组，然后只使用第 i 个元素(因此您生成了 25*25 数组，每个数组包含 25 个元素)。您可能会(事实上，极有可能)以这种方式重复某些元素。正确的 main 应该是这样的:

  int main() {
      int ddarray[25][25];
      for (int j=0; j<25; ++j)
      {
          int array[25];
          permutation(array);
          for (int i=0; i<25; i++) {
              ddarray[j][i] = array[i];
          }
      }
  }
  

  (请注意，您的原始代码中也缺少 ++j...)

• permutation 的实现效率很低，因为它必须为每个输出元素移动大量元素。标准Fischer Yates shuffle只是交换当前输出和随机选择的索引处的元素。

• 最后，我建议使用 std::array(或 std::vector)代替普通数组。后者使用起来非常不方便/令人惊讶(并且在运行时没有对不同尺寸的标准支持)。