algorithm - 在 0 和 100 亿之间以随机顺序一次选择一个数字

Question

问题

我需要在 0 到 10,000,000,000 之间一次选择一个唯一的随机数，直到选择了所有数字。本质上，我需要的行为是一个预先构建的堆栈/队列，其中包含 100 亿个随机排列的数字，无法将新项目插入其中。

不太好的解决方法:

我脑子里不乏低效的方法。比如，

• 保留生成的数字并检查新生成的随机数是否已被使用，有时这会让我们无限期地等待，直到生成可用的数字。
• 将所有可能的数字保存在一个表中并随机弹出一行并为下一次选择保留新的行数等。不确定这是好是坏。

问题:

1. 除了存储所有可能的组合和使用随机数之外，还有其他确定性方法吗？

   • 比如维护可用号码的窗口并首先随机选择一个窗口，然后在该窗口内随机选择一个号码等。例如:喜欢 this

2. 如果不是，在相当小的空间内存储数字的最佳类型是什么？

   • 50% 以上的数字不适合 32 位 (int)，64 位 (long) 是浪费。因为最大的数字适合 34 位，每个数字浪费 30 位(总共 >37GB)。

如果这个问题还没有解决。

1. 什么是存储和选择随机点并快速调整结构以加快下一次选择的良好数据结构？

*** 抱歉含糊不清。最大可选数为 9,999,999,999，最小可选数为 1。

Answer 1

你问:“除了存储所有可能的组合和使用随机数之外，还有其他确定性方法吗？”

是的，有:加密。使用给定 key 的加密可保证唯一输入的唯一结果，因为它是可逆的。每个键定义了可能输入的一对一排列。您需要对 [1..10e9] 范围内的输入进行加密。要处理这么大的东西，您需要 34 位数字，最多为 17,179,869,183。

没有标准的 34 位加密。根据您需要多少安全性以及需要多快的数字，您可以编写自己的简单、快速、不安全的四轮 Feistel Cipher或者为了更慢更安全的使用 Hasty Pudding cipher在 34 位模式下。

无论使用哪种解决方案，如果第一次加密给出的结果超出范围，只需再次加密结果，直到新结果在您想要的范围内。一对一的属性确保加密链的最终结果是唯一的。

要生成一系列看似随机的唯一数字，只需使用相同的 key 按顺序加密 0、1、2、3、4 ...。加密保证该 key 的结果是唯一的。如果您记录了自己走了多远，那么您以后可以生成更多唯一数字，直到您的 100 亿个限制。