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

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

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

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

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