寻找一种以(伪)随机顺序吐出数字序列的算法

有一个简单的函数可以生成 [0..m-1] 对于给定的 m . 选一个号码就行了 k ,相对主要到 米 让 f(i)=(k*i) mod m . 这始终会生成一个排列(在 0<=i<m )如果 K 大于 米 .

例如,m=20,设k=137(python代码, % “模”意味着:

 >>> [(137*i) % 20 for i in range(20)]
 [0, 17, 14, 11, 8, 5, 2, 19, 16, 13, 10, 7, 4, 1, 18, 15, 12, 9, 6, 3]

这是一个非常简单的prng,无法保证其统计特性。

这个问题类似于(m+1)牌的洗牌,编号为[n,…,n+m]。注意编号(因此 n )不重要,重要的是我们可以区分牌。(您可以简单地添加 n 如果需要,请稍后返回。)

要做你想做的,你可以执行 Fisher-Yates shuffle 和 just keep track of which indices have been selected 因为到目前为止还不清楚。这将允许您避免按要求存储值本身的另一个副本。

你的问题有点令人困惑,因为听起来你想把所有的原始序列都取回来,但是你有4和8映射到10,而没有映射到12。

如果你的意思是1:1映射,那么你要找的是原始集合的随机排列。有一些方法可以先收集或不收集集合(但是您需要一些生成集合的东西,或者跟踪您所在的位置)。

另外,注意n并不重要。您可以使用0,1,2,….m,然后在需要时添加n到所有内容中。

假设我已经正确地解释了这一点,并且您实际上正在寻找一种随机排列算法(即随机排列,类似于洗牌,称为随机排列),请看一下 Fisher-Yates

[编辑] 好的,根据你的更新,你面临的问题是:你不想显式地编码排列,但你必须以某种方式编码它,以便构造f。最简单的方法就是将排列索引实际存储在数组中,但是如果你不想因为某种原因(例如太大)这样做,你可以用各种方式编码它。不过,没有免费午餐,因为信息理论上限制了这种做法的简单程度。无论如何,您可以从查找“编码排列”的工作中获得一些想法,例如 this paper

以下是我自己编的语言中的一些伪代码:

function f(array a)
    array newArray
    while a.size() == 0
        int position = randomNumber(1 to a.size())
        int removedNumber = a[position]
        a.remove(position)
        newArray.insertAtEnd(removedNumber)
    end while
    return newArray

将初始值添加到列表中。
然后,使用随机数在列表当前大小的范围内选择一个新的索引值。
使用该索引选择号码,然后从列表中删除该号码。

正如有人已经指出的,这类似于拥有一副牌,然后一次随机取出一张牌。

如果你想要一个1:1的地图,按照其他答案中提到的Fisher Yates。

如果您不关心1:1映射,并且只需要从给定的序列中得到所有的结果值(有可能重复),那么您可以使用具有指定范围的随机函数。

例如,在C++中,可以用下面的方式使用RAND()。

result = rand() % (m+1) + n

所以以你为例,

result = rand() % 8 + 10

将产生一个介于10和17之间的整数。

你可以 fit a polynomial 按照选定的顺序,我猜这就是你的同事给你看的。不过,与记忆排列相比,它不会节省空间。

通过使用块密码和xor折叠,可以生成前n个整数的排列,如 my previous answer .

如果不将原始函数的结果存储在某个地方,就不可能返回值。推理:

随机数生成器告诉您从原始序列返回这些值:5、11、3。

所以你跳过前四个值,返回第五个,再跳过5个,返回第十一个…现在,如何返回第三个而不将其保存在某个位置?

你能做的最接近的事情就是创建一个列表并附加所有你跳过的值,但是这听起来很尴尬,可能不值得你这么做。此外,如果洗牌算法返回一个非常大的值,然后返回一个非常小的值(在这种情况下,您将有效地将大多数值复制到列表中,首先是要避免的值),则速度会非常慢。

我休息我的案子。

您的输入描述如下 f(x) => x + 9 或者更一般地说 f(x) => n - 1 + x 作为 x 从1点开始。

你链接到 another question 它描述了一个函数 r(x) 它将x映射到无序排列的值, 0 <= r(x) <= m .

所以 f(r(x) + 1) 或 (r(x) + n) 应该给你想要的价值。

为小 m 您还应该能够通过跟踪和错误找到标准随机数生成器的种子,然后生成 m+1 采用mod时的不同值 M+ 1 如果不想编写自己的生成器代码。