[在可能发生冲突且代价高昂时如何生成不重复的随机值？

Question

我知道有很多这样的问题，但是它们在一个关键方面似乎都不同：我的碰撞管理问题更具挑战性。

我的样本空间是aaaaa形式的序列，其中a是字母[a-z]。这样就是26 ^ 5 = 11,881,376个组合。 （请注意，我的单词大小（5）和字母大小（26）很小。这是因为我需要相当难忘的单词。这意味着我可能必须在1200万个可能的对象中分配大约一百万个，这意味着发生碰撞的可能性要比从2 ^ 32个可能的整数中选择100个整数大得多。）

此外，我需要生成一个随机值，并且它不得与任何现有值冲突，但是这些现有值是在很长一段时间内生成的，并存储在数据库中。换句话说，为了方便进行碰撞检查，我没有将它们存储在内存中。

大多数用于生成无重复值的随机值的算法包括生成一个值并仅对其进行碰撞测试，然后重复进行直到没有碰撞为止。但是这里的测试意味着数据库调用，它将更加昂贵，而我的冲突率则更高。所以我认为我会遇到问题。

有更好的方法吗？

Answer 1

使用您的宇宙很小的事实：用所有1200万个数组填充。随机排列数组，以便它们以随机顺序排列。用它们填充数据库表并对其进行索引（即，数据库行的外观类似于（1，“ hgfyu”），（2，“ aipes”），（3，“ zdpgb”）等）。

然后跟踪（在另一个表中）已分发的数量，并且当您需要另一个时，只需分发“下一个”并增加计数。

具有更多数学功能，更少存储空间的另一种可能性：只需跟踪您已分发的数量即可。然后，每当您需要一个新的RNG时，都可以使用可复制的RNG以固定的序列（称为K）查找第N个随机数，然后按字典顺序返回第K个代码。

Answer 2

通常，您将使用哈希计数器；只需将计数器保持在0到11,881,375之间，并对其应用一些双射映射功能，即可随机生成它们。

类似：

// map any value < 2**24 to another value < 2**24, with no duplicates
int hash24(int x) {
  x = x ^ (x >> 12);
  x = (x * 0x818d6b) & 0xffffff;
  x = x ^ (x >> 10);
  x = (x * 0x0fa653) & 0xffffff;
  x = x ^ (x >> 12);
  return x;
}

void next(char result[6]) {
  static int s = 0;    // keep this value somewhere persistent
  const int seq = 0x55aa55;    // change this to re-randomize
  int r;

  // find the next random value less than 26**5
  do {
    r = hash24(s ^ seq);
    s = s + 1;
  } while (result >= 11881376);

  // map integer to string of letters
  for (int i = 0; i < 5; ++i) {
    result[i] = 'a' + (r % 26);
    r /= 26;
  }
  result[5] = '\0';
}

但是，您似乎有更多未提及的约束。您可能要避免使用令人讨厌的单词，因为它们是完美的乱语（例如YouTube网址），同时，您可能希望避免使用令人反感的单词（不知道YouTube是否过滤了这些单词，但我没有看到一个）。

因为26可被二整除，所以制作一个不依赖于拒绝超出范围的值的版本相当简单，但这是不必要的奇怪的事情：

int hash26p5(int x) {
  int r[5] = { 5, 11, 17, 23, 27 };
  for (int i = 0; i < 5; ++i) {
    int r = ((x & 31) * r[i]) & 31;
    x = (x >> 5) + r * 371293;
  }
  return x;
}

void next(char result[6]) {
  static int s = 0;    // keep this value somewhere persistent
  int r hash26p5(s);
  s = s + 1;

  // map integer to string of letters
  for (int i = 0; i < 5; ++i) {
    result[i] = 'a' + (r % 26);
    r /= 26;
  }
  result[5] = '\0';
}

事实上，由于只有两个主要因素，可以完成更多有趣的事情，但是它们甚至更加神秘，如果您使用较小的字母或不同数量的字母，它们将不相关。