"Randomness Length" C 中的 srand？

Question

因此，我必须生成一个长度为 N 的 int 向量，其中只有 n 个随机元素为 1，其他元素为 0。为此，我创建了一个长度为 N 的向量，对其进行初始化，使前 n 个元素为 1，其他元素为 0，然后开始使用一个简单的函数对其进行洗牌，该函数接受一个 int 向量，生成随机数从 0 到 N 并根据 rand 的输出重新洗牌向量。我的问题是：我可以 "trust" 随机生成器给我多少次不同的数字序列，以便我每次都能得到不同的向量？如果我运行这个函数，比方说，100 万次，我是否获得了 100 万种不同的组合（前提是有超过 1m 种不同的方式来重新排序我的向量）？如果没有，我应该如何进行？有什么方法可以检查我是否正在生成以前生成的序列？

编辑：关于算法可能存在的缺陷，这里是（我在我的主函数中只执行一次 srand(time(NULL))，在调用这个函数之前）：

 void Shuffle(int vector[],int n, int N)
 {
  int i = 0;
  int j = 0;
  for(i=0;i<n;i++)
     {
      j = rand() % N;
      if(j!=i)
         swap(&vector[i],&vector[j]);
     }
  }

其中 swap 是交换向量元素的函数。我不明白为什么会有缺陷。我比其他人更有可能得到一些结果吗？我知道 Fisher-Yates Shuffle 算法，我写这个是为了节省一些时间执行...

Answer 1

你可以计算你的序列的CRC，它对顺序敏感。找到 CRC32 的 public 域实现并保存每个序列的 32 位值。如果 CRC 不同，则序列不同。如果 CRC 相同，则它们可能相同（它们有 1/4 十亿的机会具有相同的 CRC 但序列不同）。

Answer 2

如评论中所述，随机播放算法存在缺陷。您应该使用 Fisher-Yates 随机播放。算法有偏差的证明相对简单：考虑 1 和 0 的序列未被算法改变的概率。如果所选的 n 个随机数中的每一个都小于 n，则概率为 (n/N)ⁿ 或 n ⁿ/Nⁿ。正确的概率是1/(N选n)，也就是n!/(N×(N-1)×…(N-n+1))。如果n相对于N较小，则后一个表达式非常接近n!/Nⁿ。由于 nⁿ 比 n! 大很多，算法产生未改变序列的概率比它应该的大得多。（大多数但不是所有 1 在其原始位置的序列也是 over-produced，但没有那么显着。）
在任何程序中您都不应多次调用 srand（除非您真的知道自己在做什么）。 srand 为随机数生成器播种；播种后，每次需要新号码时只需调用 rand。（这一点是由问题的标题引起的，而且错误使用 srand 的事实似乎很常见。）
标准C库rand函数不提供任何质量保证，部分实现范围小，周期短，令人痛心。但它们可能足以进行一百万次随机洗牌。
即使您的随机数生成器每次都产生不同的序列，即使您修复了洗牌函数以进行适当的 Knuth-Yates 洗牌，您仍然会得到重复，因为向量正在洗牌有重复的值。结果，两个不同的洗牌可以产生相同的序列。考虑 n 为 2 的简单情况，因此您的初始向量是两个 1，后跟 N-2 个 0。这两个 1 彼此无法区分，因此如果您的第一步交换到位置 k，第二步交换到位置 l，这将产生与首先交换到 l 完全相同的结果然后到 k.

我想你真正想做的是构造一个随机的combination of n out of N objects. There are N choose n这样的可能组合；理想情况下，每个这样的组合应该以相等的概率生成。

以下是实现此目的的一些算法。都是O(N)时间，因为不可能在小于线性时间的时间内填完一个长度为N的boolean vector。但是，如果您可以只使用 1 的索引列表，那么第二种算法是 O(n)，如果您需要对索引进行排序，则为 O(n log n)。在 this answer 中引用的论文中可以找到按排序顺序生成索引的真正 O(n) 算法，如果 N 非常大而 n 相当小，则该算法可能是合适的.

以下函数被多种算法使用。它可以改进，正如它的评论所表明的那样，但它可以与良好的 RNG 一起正常工作。 rand() 不是一个好的 RNG。

/* This is not a good implementation of rand_range
 * because some rand() implementations exhibit poor randomness
 * of low-order bits. (And also the bias issue if RAND_MAX is
 * small.) Better random number generators exist :) */
/* Produces a random integer in the half-open range [lo, hi) */
int rand_range(int lo, int hi) {
  return lo + rand() % (hi - lo);
}

1。水库取样

适用于大样本量的简单算法是 reservoir sampling:

/* vec must be a vector of size at least N. Randomly
 * fills the vector with n 1s and N-n 0s.
 */ 
void random_fill(int vec[], int N, int n) {
  int i;
  for (i = 0; n; ++i) {
    if (rand_range(0, N-i) < n) {
      vec[i] = 1;
      --n;
    }
    else
      vec[i] = 0;
  }
  for (; i < N; ++i) vec[i] = 0;
}

2。改组索引

另一种可能性是通过对索引列表进行前缀洗牌来生成 1 的索引：

int random_fill(int vec[], int N, int n) {
  /* For simplicity, use a temporary vector */
  int* inds = malloc(N * sizeof *inds);
  for (int i = 0; i < N; ++i) inds[i] = i;
  for (int i = 0; i < n; ++i) {
    int j = rand_range(i, N);
    int t = inds[j]; inds[j] = inds[i]; inds[i] = t;
  }
  for (int i = 0; i < N; ++i) vec[i] = 0;
  for (int i = 0; i < n; ++i) vec[inds[i]] = 1;
  free(inds);
}

3。 Select 来自枚举序列

如果N choose n不是太大（也就是说，你可以在没有整数溢出的情况下计算它），生成随机序列的一种方法是选择一个小于N choose n的随机整数，然后使用可能序列的一些枚举产生与该序数的组合。（如果你使用 rand()，你应该知道即使 N choose n 可以计算而不会溢出，它仍然可能大于 RAND_MAX，在这种情况下 rand() 不会生成所有可能的序数。）

上述水库采样算法可以直接修改以生成枚举：

/* Fills vec with the kth sequence of n 1s and N-n 0s, using
 * an unspecified ordinal sequence; every value of k between 0
 * and (N choose n) - 1 produces a distinct sequence.
 */
void ordinal_fill(int vec[], int N, int n, int k) {
  for (int i = 0; N; ++i, --N) {
    int r = (k * n) % N;
    if (r < n) {
      vec[i] = 1;
      k = (k * n) / N;
      --n;
    } else {
      vec[i] = 0;
      k = (k * (N - n)) / N;
    }
  }
}

(live on ideone)

上面的程序没有对other的序数值做任何假设比它是正的并且适合整数。实际上，它将被采取 modulo N choose n，尽管该值从未明确计算过。如果你使用 uint64_t 而不是 int 和一个随机数生成器，它可以生成大范围内的随机数，您可以通过向函数提供随机数来生成随机序列。当然，这并不能保证序列是唯一的。

本质上，该函数通过使用序数值 (k) 作为水库采样算法所需的 "random" 数字的来源来工作。每个序数（mod N choose n）对应一个不同的序列（证明留作练习）。因为序数 space 被 modulo 而不是量级划分，所以序数序列作为序列可能不是特别有用，但它是 gua预期是一个完整的序列。

按大小划分（使用组合编号之类的东西 system) 可能更快——例如，它不需要除法——但它需要有效访问二项式数，而上述函数不需要。如果每一步都计算二项式系数，那么就需要除法，这样会失去很多速度优势。

Answer 3

给所有可能的序列编号（阅读 enumeration part of the Wikipedia article about combinations），然后 select 每个顺序（随机化后可选）。

#1   - 1 1 1 1 1 1 1 1 0 0 0
#2   - 1 1 1 1 1 1 1 0 1 0 0
#3   - 1 1 1 1 1 1 1 0 0 1 0
#4   - 1 1 1 1 1 1 1 0 0 0 1
#4   - 1 1 1 1 1 1 0 1 1 0 0
...
#165 - 0 0 0 1 1 1 1 1 1 1 1

Answer 4

很多 PRNG 的周期长度是已知的，例如参见 Amy Glen "On the Period Length of Pseudorandom Number Sequences" [2002] 的论文。你的 LibC 的实际 rand() 实现的时期是未知的，你需要在源代码中查找它（例如：glibc-2.22/stdlib/rand_r.c）并自己计算它（论文中的 howto以上）或文档（不太可能）。

请注意，您需要 x * N 的时间段，其中 x 新打乱的向量的数量和 N 该向量的长度，而且显然，机会两次洗牌导致相同结果与 N 的大小成反比，也就是说，N 越小，获得两个相等向量的机会就越大。

如果您想将风险降至最低，您需要具有良好且有保证的雪崩的东西，例如加密校验和。它们在计算上很昂贵，但您可以直接使用总和（您说您只需要零和一个）并在必要时连接。非常小 'N' 的问题不会消失，但会最小化。

这也有点取决于你打算做什么，你需要它做什么。有时，尤其是使用 Monte Carlo 方法时，一种 PRNG 似乎比另一种得到更好的结果。

[2002] 艾米格伦。 "On the Period Length of Pseudorandom Number Sequences." 澳大利亚阿德莱德大学 (2002)。 thesis.pdf 可用（2016.08.18 下载）

Answer 5

If I run this function, let's say, 1 million times, do I obtain 1 million different combinations (?)

OP 有代码

srand(time(NULL)); // only once in my main function

time() 通常 returns 秒的整数计数。然后对该程序的任何调用 - 在同一秒内 - 都会产生相同的结果，因此测试可能需要等待大约 12 天才能测试 100 万个组合。

即使使用另一个来源调用srand(unsigned seed)，seed也只接受[0...UINT_MAX]的值，可能只有65,636个不同的值。（通常 unsigned 有 4,294,967,296 个不同的值）。

验证 unsigned 的范围并考虑 "random" 初始化的其他来源，例如进程 ID 或 dev/random

"Randomness Length" C 中的 srand？

"Randomness Length" of srand in C?

c

random

vector

srand

1。水库取样

2。改组索引

3。 Select 来自枚举序列