c++ - 减少随机播放算法中调用rand的次数

Question

我已经实现了Fisher-Yates算法来随机地对我的数组进行洗牌。
目前，我要调用rand()函数8次。我的问题是:我怎么只能调用rand()函数6次。
这是我的实现:

class numbers{
private:
    static int indexCount;
    vector <vector <int> > list;
    vector<int> temp;

public:

    void swap (int *a, int *b)  
    {  
      int temp = *a;  
      *a = *b;  
      *b = temp;  
    }  

    int randomize (int arr[], int n)  
    {  
      RandomCount=0;

      for (int i = n - 1; i > 0; i--)  
      {  
          int j = rand() % (i + 1);  
          RandomCount++;
          swap(&arr[i], &arr[j]);  
      }
    }

我试图计算调用rand()函数的次数，由于循环，调用次数为8，但是我试图将这个数字降低到6，同时仍然使数组随机化。

该数组包含值{1,2,3,4,5,6,0,0,0}。我注意到，因为数组中有3个0，所以无需使用rand()函数就可以交换它们。但是，我不确定该怎么办。

Answer 1

首先，我会说rand()通常不适合作为随机数生成器-它通常不是很好，它依赖于隐藏的全局状态，并且使用rand() % n会引入偏差。从C++ 11开始，最好使用<random>中提供的随机数生成器； see this Q&A for an example。

不过，以您的示例为例，我假设您的限制是对rand()的六个调用，而不一定是六个随机数。因此，我们可以利用rand()的范围(RAND_MAX，至少32767)的范围远大于您希望生成的数字的大小(在这种情况下，最多为9)。那么，为什么不一次生成两个数字呢？

例如，如果我们需要获得A = [0,4)和B = [0,3)范围内的两个随机数，则可以使一个随机数成为X = [0, 4 * 3) = [0,12)范围内的一个随机数。然后，我们可以将A = X % 4 = [0,4)和B = X / 4 = [0,3)作为均匀分布的随机变量。

这样做使我们可以对rand()的每个调用执行两个步骤。那么，对于长度为9的数组，我们有9 = 4*2 + 1，因此我们只能通过对rand() 的 5个调用来避免。

翻译循环:

RandomCount = 0;
int i = n - 1;

// first do the leftover element, if we have an odd array length
if (n % 2) {
  // (this is a terrible way to generate random numbers, but I'll stick with it)
  int j = rand() % (i + 1);
  RandomCount++;
  swap(&arr[i], &arr[j]);
  i--;
}

// now do the rest, two at a time
for (; i > 0; i -= 2)  
{  
  // get our two random numbers
  int r = rand() % ((i + 1) * i);
  RandomCount++;
  int a = r % (i + 1);  // number in [0, i+1)
  int b = r / (i + 1);  // number in [0, i)

  // do two swaps
  swap(&arr[i], &arr[a]);
  swap(&arr[i-1], &arr[b]);
}

通过使用更多的随机数，您甚至可以做得更好。但是请注意，这仅适用于足够小的n大小:如果使用n * (n-1) > RAND_MAX，则会遇到问题，因为您将无法生成足够大的随机数。

为了让您了解拆分为何起作用，让我们考虑一下我们获得的两个值。假设我们要获取A = [0,X)和B = [0,Y)范围内的值。我们生成一个范围为R = [0, X * Y)的数字。

我们可以说A = R % Y = [0, Y)。 %运算符是模或余数(对于正数)运算符。也就是说，除以Y，我们还剩下多少？可能的值是从0(Y平均分配)到Y-1的所有数字。此外，由于R中最小的数字是0，最大数量比Y的倍数小1，因此它是均匀分布的。

我们可以说B = R / Y = [0, X)。使用整数下位除法，R中从0到Y-1的任何数字都映射到0中的B，从Y到2Y-1的任何数字都映射到1中的B，依此类推。这就是我们的最大值XY-1，它精确地映射到X-1。

您可以将其视为一个填充的二维数字表，其中包含X行和Y列。 R选择一个随机索引到表中。当您使用R / Y时，您将获得哪一行；当您使用R % Y时，您将获得哪一列。