5

假设我有一个数字序列：{n, n+1, n+2, ... n + m}

在不提前存储数字的情况下，我想创建一个函数 f()，它给定序列 {1,2,3,...m} 将以随机（或至少伪随机）顺序吐出原始集合.

例如假设我的序列是 {10, 11, 12, 13, 14, 15, 16, 17}

   f(1) 可以产生 14
   f(2) 可以产生 17
   f(3) 可以产生 13
   f(4) 可以产生 10
   f(5) 可以产生 16
   f(6) 可以产生 15
   f(7) 可以产生 11
   f(8) 可以产生 12

在过去的某个时刻，一位同事向我展示了一种能够做到这一点的数学算法，但我几乎忘记了除了它存在之外的所有东西。我记得你必须事先有序列，并从函数中使用的序列中生成一些常量。对于那些想知道的人，我很遗憾与那位同事失去了联系。

这个问题的答案看起来接近我想要的，但我不确定答案是否允许我提前将输出限制为特定序列。

编辑：

为了澄清一点，我不想存储原始序列或打乱的序列。我想从原始序列生成一个函数 f() 。

令人沮丧的是我已经看到了这个，我只是记不住它，无法用谷歌再次找到它。

Fisher-Yates 算法非常适合置换或洗牌，但这不是我想要的。

4

10 回答 10

7

有一个简单的函数可以[0..m-1]为给定的 生成 的排列m。只需选择一个k相对质数的数字m并让f(i)=(k*i) mod m。这总是会产生一个排列（在 上没有重复0<=i<m）。如果k大于则效果更好m。

例如，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，不能保证它的统计特性。

于 2009-04-09T10:07:06.790 回答
3

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

如果您实际上的意思是 1:1 映射，那么您正在寻找的是原始集合的随机排列。有一些方法可以先收集或不收集集合（但您需要生成它的东西，或跟踪您所在的位置）。

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

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

[编辑]好的，根据您的更新，您面临的问题是：您不想明确编码排列，但您必须以某种方式对其进行编码才能构造 f。最简单的方法就是将排列后的索引实际存储在一个数组中，但如果您出于某种原因（例如太大）不想这样做，您可以以各种方式对其进行编码。但是，没有免费的午餐，因为信息理论限制了这有多简单。无论如何，您可以通过查找有关“编码排列”的工作获得一些想法，例如本文

于 2009-04-09T04:00:25.470 回答
3

这个问题类似于洗一副 (m + 1) 张牌，编号为 [n, ..., n + m]。请注意，编号（因此n）并不重要；重要的是我们可以将卡片区分开来。（如果需要，您可以稍后简单地添加n背面。）

要执行您想要的操作，您可以执行Fisher-Yates 洗牌，并跟踪到目前为止已选择哪些索引进行洗牌。这将允许您避免根据要求存储值本身的另一个副本。

于 2009-04-09T04:06:58.997 回答
0

这是我自己编造的一些伪代码：

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
于 2009-04-09T03:54:49.323 回答
0

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

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

于 2009-04-09T04:17:26.570 回答
0

如果您想要 1:1 映射，请使用其他答案中提到的 Fisher-Yates。

如果您不关心 1:1 映射，并且您只需要所有结果值都来自给定序列（可能重复），那么您可以使用具有指定范围的随机函数。

例如，在 C++ 中，您可以通过以下方式使用 rand() -

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

所以对于你的例子，

result = rand() % 8 + 10

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

于 2009-04-09T04:26:17.857 回答
0

您可以将多项式拟合到所选序列；我猜这就是你的同事给你看的。不过，与仅记住排列相比，它不会节省空间。

于 2009-04-09T05:44:08.467 回答
0

根据我之前的回答，您可以使用分组密码和 xor 折叠来生成前 n 个整数的排列。

于 2009-04-09T08:12:58.703 回答
0

您的输入由 描述f(x) => x + 9，或更一般f(x) => n - 1 + x地x从 1 开始。

您链接到另一个问题，该问题描述了r(x)将 x 映射到混洗值的函数0 <= r(x) <= m。

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

对于 small m，您还应该能够通过跟踪和错误找到标准随机数生成器的种子，然后如果您不想编写自己的生成器，则m+1在使用 mod 时会生成不同的值。m+1

于 2009-04-09T09:43:47.657 回答
0

如果不将原始函数的结果存储在某处，就不可能返回这些值。推理：

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

因此，您跳过前四个值，返回第 5 个，跳过另一个 5，返回第 11 个……现在如何返回第 3 个而不将其保存在某处？

您可以摆脱的最接近的事情是创建一个列表并附加您跳过的所有值，但这听起来很尴尬并且可能不值得努力。此外，在改组算法返回一个非常大然后非常小的值的情况下，它会非常慢（在这种情况下，您首先会有效地将大多数值复制到列表中，这是您想要避免的）。

我休息一下。

于 2009-04-09T10:33:21.783 回答