我已经实现了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}。我注意到，因为我的数组中有三个0，所以我可以在不使用rand()函数的情况下交换它们。然而，我不知道该怎么办。
首先，我要说的是，rand()通常不被认为是一个随机数生成器——它通常不是一个很好的生成器，依赖于隐藏的全局状态，并且使用rand() % n会引入偏差。由于C++11，您最好使用<random>中提供的随机数生成器；请参阅此问答；A是一个例子。
不过，坚持你的例子，我假设你的限制是对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，因此我们只需要5次对rand()的调用。
翻译你的循环：
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的倍数少一，因此它是均匀分布的 - 我们可以说
B = R / Y = [0, X)。通过整数楼层划分，R中从0到Y-1的任何数字映射到B中的0，从Y到2Y-1的任何数字在B中映射到1，依此类推。这就达到了我们的最大值XY-1，它精确地映射到X-1
您可以将其视为一个填充的二维数字表，其中包含X行和Y列。CCD_ 48在表中选择一个随机索引。取R / Y得到的是哪一行，取R % Y得到的是那一列。
简介
我使用了这样一个事实，即2^N个可能值的均匀分布只需要N位熵就可以真正随机。如果我们假设产生这些比特的随机过程足够随机，那么我们可以使用对rand()的不到一半的单个调用来生成[0，8)、[0，4)和[0，2)分布(每个分布3、2和1比特)
问题设置
rand()生成一个介于0和rand_MAX之间的伪随机数，这是实现定义的，但保证至少为32767，或十六进制，介于[0x000,0x7fff]之间(包括0x0000,0x7ff)。因此，rand()可以被认为提供了15个随机比特：15个比特的熵。我不是随机性专家，众所周知，rand()不是足够随机的，所以对rand()的一次调用可能会产生不到15位的熵。但我不是一个聪明的人，我无法解释这些局限性。因此，在宏大的学术传统中，我会把它们拿走。为了这个答案的目的，rand()产生15个真正唯一的熵比特。
因此，我们假设rand()的6个调用产生6 x 15=90比特的熵。
对一副8张牌进行洗牌可以生成9!(9阶乘)排列：362880张可能的牌的唯一排列。362880个排列需要CCD_ 58的熵。这远远低于我们的90位池。然而，我们需要这些额外的比特来减少我们的一些随机选择中的偏差，正如我们将看到的，因为90 bits不能完全被log2(362,880) bits整除。
这是我们的随机比特池：
[ r00 | r01 | ... | r13 | r14 ] <-- lower 15 bits from first call to rand()
[ r15 | r16 | ... | r28 | r29 ] <-- lower 15 bits from second call to rand()
o
o
o
[ r75 | r76 | ... | r88 | r89 ] <-- lower 15 bits from sixth call to rand()
每次迭代需要多少位
让我们看看理论上每次迭代shuffle算法需要多少比特。
对于我们的9张牌组，根据Fisher Yates的说法，第一次迭代以相同的概率从9张牌中选择一张，并将其放置在牌组的末尾。为了从9个选项中随机选择一个，我们需要熵的log2(9) = ~3.2 bits。
第二次迭代以相同的概率从剩下的8张牌中选择一张，并将其放置在牌组的新一端。为了从8个选项中随机选择一个，我们需要熵的log2(8) = 3 bits。
我们仔细检查所有的选择，看看每一步需要多少比特：
Iteration | Choices | Bits Required
----------+---------+--------------
0 | 9 | about 3.17
----------+---------+--------------
1 | 8 | exactly 3
----------+---------+--------------
2 | 7 | about 2.81
----------+---------+--------------
3 | 6 | about 2.58
----------+---------+--------------
4 | 5 | about 2.32
----------+---------+--------------
5 | 4 | exactly 2
----------+---------+--------------
6 | 3 | about 1.58
----------+---------+--------------
7 | 2 | exactly 1
----------+---------+--------------
8 | 1 | exactly 0
对于需要整数位数的迭代(即步骤1、5和7，每个步骤都有2^3、2^2和2^1个可能值)，我们只需要精确的位数就可以选择这些值。我们的第一个rand()调用有15位熵，我们可以使用！就拿其中的6个吧。我们还有84个比特可以根据需要分配给其他迭代。对于这三种特殊情况，我们只需调用rand()一次，就可以获得所需的位。
我们应该为其他5次迭代(即步骤0、2、3、4和6)分配多少位？好吧，代码的天真实现只会在每次迭代中使用15位(因为每次调用rand()都会产生15位熵)。如果那是"；足够随机"；对于您最初想要的内容，我们可以对这5次迭代中的每一次都这样做。这个代码看起来是这样的：
一种实现
// changed return type to void since this doesn't return anything
void randomize (int arr[], int n)
{
// generate our bit pool for uniform distributions of size 2^n
int integral_rand_pool = rand();
for (int i = n - 1; i > 0; i--)
{
int j;
if (i == 7)
{
// need 3 bits of entropy
j = integral_rand_pool & 0x07;
integral_rand_pool = integral_rand_pool >> 3;
}
else if (i == 3)
{
// need 2 bits of entropy
j = integral_rand_pool & 0x03;
integral_rand_pool = integral_rand_pool >> 2;
}
else if (i == 1)
{
// only need 1 bit of entropy
j = integral_rand_pool & 0x01;
integral_rand_pool = integral_rand_pool >> 1;
}
else
{
// need a non-integral number of bits. Just grab 15 from rand()
j = rand() % (i + 1);
}
swap(&arr[i], &arr[j]);
}
}
这通过仅调用rand()6次，以与调用rand()8次相同的偏移量完成了问题。
我们能减少我们的偏见吗
如果我们有N个随机位，并且我们想要产生一个[0，M)之间的数字，并且我们通过产生一个[0]，(2^N)-1]之间的随机数并取模M来产生我们的随机数，那么如果(2^N)不是M的倍数，我们将总是倾向于选择范围低端的数字。我们可以通过增加N来减少这种偏差。
如果我们想减少我们的偏差，那么，最简单的方法就是增加我们在每个非积分熵步骤中使用的比特数。我们增加多少？从上面我们知道，我们总共有90个熵位。我们的三次迭代分别取了其中的6个比特，并且没有产生偏差。这为我们剩下的5次迭代留下了84个比特，或者每次迭代刚好超过16个比特。我们的第一个rand()池中有9个我们不使用的位。
如果我们只取其中一个比特，并将其附加到每个非积分比特值的rand()的结果中，我们可以稍微减少每个数字的偏差。在这之后，我们还有四个比特，对如何测量随机数中的偏差进行更深入的研究可以用来确定哪一次迭代更值得额外的比特。但在这一点上，它看起来非常复杂，最好使用标准的<random>库。
请参阅链接以获取更多信息。