给定一个数字，生成另一个随机数，每次都是相同的，并且与其他所有结果不同 [英] Given a number, produce another random number that is the same every time and distinct from all other results

问题描述

基本上，我想帮助设计一个算法，该算法需要一个给定的数字，并返回一个与第一个数字无关的随机数。规定a）给定的输出数对于相似的输入数总是相同的，并且b）在一定的范围内（例如1-100），所有的输出数是不同的。也就是说，没有两个不同的100以下的输入数字会给出相同的输出数字。

我知道创建一个有序的数字列表很容易，然后返回输入的索引。但我想知道它是否可以在没有任何缓存的情况下完成。也许用某种哈希算法？主要原因在于，如果可能产出的范围要大得多，比如10000000000，那么生成整个范围的数字然后随机随机洗牌将会很荒谬，如果你只能得到一些结果它。

无论它在哪种语言中完成，我只是想知道它是否可能。我一直在考虑这个问题很长一段时间，除了我已经提出的解决方案之外，我想不出一个解决方案。

编辑：I只是有另一个想法;使用另一个算法返回第一个算法的逆向算法会很有趣。是否可能会是一个有趣的挑战。

解决方案

这听起来像一个非重复的随机数发生器。有几种可能的方法来解决这个问题。

正如 p 并满足 p％4 = 3 足够大（大于输出范围中的最大值）并以这种方式生成它们：

  int randomNumberUnique（int range_len，int p，int x）
 if（x * 2< p）
 return（x * x）％p 
 else 
 return p  - （x * x）％p 
  

这个算法将覆盖 [0，p）。

中的输入， [0，p）中的所有值b $ b

Basically, I would like help designing an algorithm that takes a given number, and returns a random number that is unrelated to the first number. The stipulations being that a) the given output number will always be the same for a similar input number, and b) within a certain range (ex. 1-100), all output numbers are distinct. ie., no two different input numbers under 100 will give the same output number.

I know it's easy to do by creating an ordered list of numbers, shuffling them randomly, and then returning the input's index. But I want to know if it can be done without any caching at all. Perhaps with some kind of hashing algorithm? Mostly the reason for this is that if the range of possible outputs were much larger, say 10000000000, then it would be ludicrous to generate an entire range of numbers and then shuffle them randomly, if you were only going to get a few results out of it.

Doesn't matter what language it's done in, I just want to know if it's possible. I've been thinking about this problem for a long time and I can't think of a solution besides the one I've already come up with.

Edit: I just had another idea; it would be interesting to have another algorithm that returned the reverse of the first one. Whether or not that's possible would be an interesting challenge to explore.

解决方案

This sounds like a non-repeating random number generator. There are several possible approaches to this.

As described in this article, we can generate them by selecting a prime number p and satisfies p % 4 = 3 that is large enough (greater than the maximum value in the output range) and generate them this way:

int randomNumberUnique(int range_len , int p , int x)
    if(x * 2 < p)
       return (x * x) % p
    else
       return p - (x * x) % p

This algorithm will cover all values in [0 , p) for an input in range [0 , p).

这篇关于给定一个数字，生成另一个随机数，每次都是相同的，并且与其他所有结果不同的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！