在一系列算法不重复的随机搜索

问题描述

我在寻找产生随机数的范围内，没有重复的高效算法。

I'm looking for an efficient algorithm that produces random values within a range, without repetitions.

在伪code：（类兰德）

In pseudo-code: (in class 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（返回）应该总是从那些previously返回不同的数字。
当然，如果来 - 从+ 1 返回了数字，算法应该重新开始（或下降错误 - 反正不重要）。

The numbers returned from r.getNumber() should always be different from the ones previously returned.
Of course, if to - from + 1 numbers were returned, the algorithm should start again (or fall in error - not important anyway).

请注意，该范围可能非常大，并且因此一个随机排列阵列（含有最初 [从，到] 数）是可能溢出存储器

Note that the range may be very large, and thus a randomly arranged array (containing initially [from, to] numbers) is likely to overflow the memory.

推荐答案

一个暗号是一个一对一的映射，否则就无法解密。因此，任何块暗号将映射数字0，1，2，3，4，5，...不同的n位数字，其中n是在比特暗号的块大小。

A cypher is a one-to-one mapping, otherwise it couldn't be decrypted. Hence, any block cypher will map the numbers 0, 1, 2, 3, 4, 5, ... to different n-bit numbers, where n is the cypher's block size in bits.

这是比较容易的放在一起简单的4轮次Feistel暗号使用任何你想要的（偶数）块的大小。只有四个回合这将是快，但不安全。另外也可以使用冬冬布丁暗号它可以有pretty的，你要多任何的块大小。

It is relatively easy to put together a simple 4-round Feistel cypher with whatever (even) block size you want. With only four rounds it would be fast but insecure. Alternatively use the Hasty Pudding cypher which can have pretty much any block size you want.

无论暗号你用，只是加密数字0，1，2，...，并期待在输出块。你可以扔掉超出你的要求的范围内的任何结果，所有结果都保证是独一无二的。

Whatever cypher you use, just encrypt the numbers 0, 1, 2, ... and look at the output block. You can throw away any results that are outside your required range and all results are guaranteed unique.

这篇关于在一系列算法不重复的随机搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！