返回很大范围内的非重复随机值

我想要一个函数，它可以从一组 n 个整数（0 到 n-1）中生成 k 个伪随机值，而不重复任何先前的结果。 k小于或等于n。O(n) 内存不可接受由于尺寸较大n以及我需要重新洗牌的频率。

这些是我到目前为止考虑过的方法：

Array： 通常，如果我想要无重复的随机值，我会打乱数组，但这是 O(n) 内存。 n 可能太大而无法正常工作。

long nextvalue(void) {
  static long array[4000000000];
  static int s = 0;
  if (s == 0) {
    for (int i = 0; i < 4000000000; i++) array[i] = i;
    shuffle(array, 4000000000);
  }
  return array[s++];
}

n态PRNG： 有多种随机数生成器，可以将其设计为具有以下周期：n并参观n那个时期的独特状态。最简单的例子是：

long nextvalue(void) {
static long s = 0;
static const long i = 1009; // assumed co-prime to n
  s = (s + i) % n;
  return s;
}

这样做的问题是，对于给定的情况，动态设计一个好的 PRNG 并不一定容易。n，如果 PRNG 没有很多可变参数（甚至更难设计），它就不太可能近似公平的洗牌。但也许有一个我不知道的好东西。

m位哈希： 如果集合的大小是 2 的幂，那么就有可能设计出完美的哈希函数f()它执行从范围内的任何值到范围内的某个其他值的 1:1 映射，其中每个输入都会产生唯一的输出。使用这个函数我可以简单地维护一个静态计数器s，并将生成器实现为：

long nextvalue(void) {
  static long s = 0;
  return f(s++);
}

这并不理想，因为结果的顺序由以下因素决定f()，而不是随机值，因此它会遇到与上述相同的问题。

NPOT 哈希： 原则上我可以使用与上面相同的设计原则来定义一个版本f()它可以在任意基础上工作，甚至可以在与所需范围兼容的复合基础上工作；但这可能很困难，而且我很可能会出错。相反，可以为大于或等于的下一个二的幂定义一个函数n，并在此结构中使用：

long nextvalue(void) {
  static long s = 0;
  long x = s++;
  do { x = f(x); } while (x >= n);
}

但是这个still有同样的问题（不太可能给出公平洗牌的良好近似值）。

有没有更好的方法来处理这种情况？或者也许我只需要一个好的功能f()高度参数化且易于设计以准确访问n离散状态。

我正在考虑的一件事是类似哈希的操作，我设法获得第一个j通过精心设计的映射，结果完全随机，然后之间的任何结果j and k会简单地推断该模式（尽管以可预测的方式）。价值j然后可以选择在公平洗牌和可容忍的内存占用之间找到折衷方案。

首先，对任何使用 O(n) 内存的东西打折扣，然后讨论引用底层数组的解决方案似乎是不合理的。你有一个数组。洗牌。如果这不起作用或不够快，请向我们提出相关问题。

您只需执行一次完整的随机播放。之后，从索引中提取n，将该元素与随机位于其之前的元素交换并增加n，模元素计数。例如，对于如此大的数据集，我会使用像这样的东西 https://gist.github.com/Sebbyastian/40be860d95f9df95f319a2f17dc74dde.

质数是哈希的一种选择，但可能与您想象的不同。使用两个梅森素数 (low and high， 也许0xefff and 0xefffffff）你应该能够想出一个更通用的哈希算法。

size_t hash(unsigned char *value, size_t value_size, size_t low, size_t high) {
    size_t x = 0;
    while (value_size--) {
        x += *value++;
        x *= low;
    }
    return x % high;
}
#define hash(value, value_size, low, high) (hash((void *) value, value_size, low, high))

例如，对于大于大约两个八位位组的所有输入，这应该产生相当好的分布，但零字节前缀有一个小麻烦的例外。您可能想以不同的方式对待它们。