algorithm - 范围算法中的非重复随机搜索

Question

我正在寻找一种能够在一定范围内生成随机值且不重复的高效算法。

在伪代码中:(在 Rand 类中)

  Rand(long from, long to) {
    this.from = from;
    this.to = to;
    // ...
  }

  long getNumber() {

    // returns a random number in the [from, to] range
    //  which has never been returned before
  }

用法:

  Rand r = new Rand(1, 100000000);

  long x = r.getNumber();
  long y = r.getNumber();
  ...

从 r.getNumber() 返回的数字应该始终与之前返回的数字不同。
当然，如果返回了 to - from + 1 数字，则算法应该重新开始(或者出错 - 无论如何都不重要)。

请注意，范围可能非常大，因此随机排列的数组(最初包含 [from, to] 数字)很可能会溢出内存。

Answer 1

密码是一对一的映射，否则无法解密。因此，任何 block 密码都会将数字 0、1、2、3、4、5...映射到不同的 n 位数字，其中 n 是密码的 block 大小(以位为单位)。

将一个简单的 4 轮 Feistel 密码与您想要的任何(偶数) block 大小放在一起相对容易。只有四轮，它会很快但不安全。或者使用 Hasty Pudding cypher它几乎可以有任何你想要的 block 大小。

无论您使用什么密码，只需加密数字 0、1、2...，然后查看输出 block 。您可以丢弃超出所需范围的任何结果，并且保证所有结果都是唯一的。