给定一个数字，产生另一个随机数字，该数字每次都相同且与所有其他结果不同。

Question

给定一个数字，产生另一个随机数字，该数字每次都相同且与所有其他结果不同。

3

基本上，我希望设计一个算法，它接受一个给定的数字，并返回一个与第一个数字无关的随机数。限制条件是a）相似的输入数字将始终产生相同的输出数字，b）在某个范围内（例如1-100），所有输出数字都是不同的，即，在100以下的两个不同的输入数字不会产生相同的输出数字。

我知道通过创建一个有序的数字列表，随机洗牌，然后返回输入的索引很容易实现。但我想知道是否可以完全没有缓存地完成。也许使用某种哈希算法？主要原因是如果可能输出的范围更大，比如说10000000000，那么如果你只能得到几个结果，生成整个数字范围然后随机洗牌就会变得荒谬。

无论用什么语言，我只想知道是否可能。我已经思考这个问题很长时间了，除了我已经想出的解决方案，我想不出其他的解决方法。

编辑：我刚刚想到另一个想法；有另一个算法返回第一个算法的反转结果将是一个有趣的探索挑战，无论它是否可能。

- Maurdekye

你可以通过一些简单的计算和缓存某些信息（主要是返回输入X的随机数，以便您可以获得所请求的一致返回值）来实现。 - MaxOvrdrv

1

我希望完全不进行任何缓存。此外，该算法可能会在一段时间后变得低效，因为需要多次生成随机结果以确保它不匹配其他答案。此外，这种方法无法保持运行时间的相似性。纯数学结果不仅会为不同运行时间之间的输入提供相同的输出，而且在完全不同的计算机上也是如此。这就是我正在寻找的解决方案。 - Maurdekye

不，我不是吉姆。输入和输出的数字除了算法之外应该没有任何关系。它应该类似于随机生成算法。 - Maurdekye

1

这个问题很奇怪。你要求一组数字之间存在某种关系，但是这些数字除了这种关系之外没有其他联系。我无法想象如何区分那些相关数字除了这种关系之外没有其他联系的关系和那些相关数字在其他方面也有联系的关系。该如何开始回答这个问题呢？ - Eric Lippert

您可以尝试使用Skip32加密（警告：不要用于实际加密），但乘法逆元会更加适合。 - Brian

显示剩余5条评论

3个回答

0

你不能完全没有关联（特别是如果你想要反向也生效的话）。

有一个“模反元素”的概念，但只有当“范围”是质数时才适用，例如100不适用，你需要101（一个质数）。如果你想要伪随机数，那么这个方法可以提供给你。

以下是模反元素的概念：

如果有两个数字a和b，满足

(a * b) % p = 1

其中 p 为任何数字，那么

a and b are modular inverses of each other.

为了使这个成立，如果我们需要找到关于数字p的模反元素a，那么a和p必须是互质的，即gcd(a,p) = 1

因此，为了使所有范围内的数字都有模反元素，范围边界必须是一个质数。

范围边界为101的一些输出将是：

1 == 1
2 == 51
3 == 34
4 == 76
etc.

编辑：

嘿...实际上你知道吗，你可以使用模反元素和@Paul定义的方法的组合方法。由于每对数字都是唯一的且所有数字都被覆盖，因此您的随机数可以是：

random(k) = randomUniqueNumber(ModuloInverse(k), p)      //this is Paul's function

- vish4071

非常有趣。尽管你似乎有一个相对完整的答案，但我也被链接到了这篇文章(http://ericlippert.com/2013/11/14/a-practical-use-of-multiplicative-inverses/)，它似乎表明可以拥有任意大小且不是质数的范围。我会继续研究这个问题，除非你有什么要说的。 - Maurdekye

@Maurdekye，请查看编辑（在答案中）。它可能会有所帮助。 - vish4071

0

以下是C#的一个示例：

    private void DoIt()
    {
        const long m = 101;
        const long x = 387420489; // must be coprime to m

        var multInv = MultiplicativeInverse(x, m);

        var nums = new HashSet<long>();
        for (long i = 0; i < 100; ++i)
        {
            var encoded = i*x%m;
            var decoded = encoded*multInv%m;
            Console.WriteLine("{0} => {1} => {2}", i, encoded, decoded);
            if (!nums.Add(encoded))
            {
                Console.WriteLine("Duplicate");
            }
        }
    }

    private long MultiplicativeInverse(long x, long modulus)
    {
        return ExtendedEuclideanDivision(x, modulus).Item1%modulus;
    }

    private static Tuple<long, long> ExtendedEuclideanDivision(long a, long b)
    {
        if (a < 0)
        {
            var result = ExtendedEuclideanDivision(-a, b);
            return Tuple.Create(-result.Item1, result.Item2);
        }
        if (b < 0)
        {
            var result = ExtendedEuclideanDivision(a, -b);
            return Tuple.Create(result.Item1, -result.Item2);
        }
        if (b == 0)
        {
            return Tuple.Create(1L, 0L);
        }
        var q = a/b;
        var r = a%b;
        var rslt = ExtendedEuclideanDivision(b, r);
        var s = rslt.Item1;
        var t = rslt.Item2;
        return Tuple.Create(t, s - q*t);
    }

该程序会根据输入范围 0-100 生成在 0-100 范围内的数字。每个输入都会产生一个唯一的输出。

它还展示了如何使用乘法逆来反向处理。

您可以通过增加 m 的值来扩展范围。x 必须与 m 互质。

代码来源于 Eric Lippert 的文章 A practical use of multiplicative inverses，以及该系列中的几篇先前的文章。

- Jim Mischel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user4668606 · Accepted Answer

这似乎是一个非重复的随机数生成器。有几种可能的方法可以实现。

如文章所述，我们可以通过选择一个足够大（大于输出范围的最大值）的素数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)内的输入。