以随机顺序生成整数序列，而无需预先构建整个列表

Question

如何从1到N生成整数列表，但是是以随机顺序生成，而不会在内存中构建整个列表？

（要明确：在所生成的列表中的每个号码必须只出现一次，所以它必须是等同于第一创建在存储器中的整个列表，然后混洗。）

这已被确定为是重复的this question。

Answer 1

您将需要至少一半的列表内存，只是为了记住你已经做了什么。

如果你在艰难的内存条件下，您可以尝试这样：

1. 保持在树至今所产生的结果，随机的数据，并将其插入到树。如果你不能插入，然后生成另一个数字，然后再试一次，等等，直到树中途填满。

2. 当树填满一半时，你反转它：你构造一棵树，它拥有你尚未使用的数字，然后以随机顺序选取它们。

它有一些保留树结构的开销，但它可能有助于指针的大小比数据小得多。

Answer 2

它可能有助于指定您正在寻找解决方案的语言。

您可以使用动态列表来存储您生成的数字，因为您需要一个参考数字，您已经创建了这些数字。每当您创建一个新号码时，您都可以检查该号码是否包含在列表中，如果包含该号码并将其丢弃，请重试。

没有这样的列表的唯一可能的方法是使用一个数字大小，如果算法正常工作不会产生重复，如UUID - 但这并不能保证没有重复产生 - 它是不太可能的。

Answer 3

非常简单的随机是1 +（（power（r，x）-1）mod p）将从1到p对于从1到p的x的值并且将是随机的，其中r和p是素数，并且r <> p。

Answer 4

技术上不是整个列表，但您可以使用位掩码来决定是否已选择一个数字。这比存储列表本身的存储空间少得多。

将所有N个位为0，则对于每个期望数目：

• 正常使用线性同余方法之一从1选择的数N.
• 如果该号码已被使用，找到下一个最高未使用（0比特），并换行。
• 将数字位设置为1并返回。

这样你就可以保证每个数字只有一个使用和相对随机的结果。