寻找一种算法以（伪）随机顺序吐出数字序列

StackOverflow https://stackoverflow.com/questions/732700

题

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

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

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

   f(1) could yield 14
   f(2) could yield 17
   f(3) could yield 13
   f(4) could yield 10
   f(5) could yield 16
   f(6) could yield 15
   f(7) could yield 11
   f(8) could yield 12

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

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

编辑：

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

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

Fisher-Yates 算法非常适合排列或洗牌一副牌，但这不是我想要的。

有帮助吗？

解决方案

有是产生[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，没有关于其统计特性保证。

其他提示

此问题是类似于混洗的第（m + 1）卡，编号为[N，...，N + M]的甲板。注意，编号（以及因此n）是不重要的;重要的是，我们可以分辨出牌。 （可以简单地添加n如果需要稍后再试。）

要你想要什么，你可以执行 费雪耶茨洗牌 和的只要保持其索引的轨道已被选择 迄今洗牌。这将允许您避免存储值本身的另一个副本，作为请求。

您的问题是有点混乱，因为它听起来像你想获得的所有原始序列的后面，但你同时拥有4,8映射到10，并没有映射到12。

如果你实际上意味着是一个1：1的映射，那么你正在寻找的是原设定的随机排列。有办法带或不带先收集了一组（但你需要的东西产生，或者跟踪你在哪里的）来做到这一点。

此外，请注意n是不重要的。您可以随时使用0,1,2，...，M，然后根据需要加入正的一切。

假设我正确地解释这一点，你实际上是在寻找一个洗牌的算法（即随机排列，称为慢腾腾通过类比洗牌一副扑克牌），看看的费 - 耶茨

[编辑] 好了，根据您的更新，你所面临的问题是：你不想置换进行明确编码，但必须以构建˚F莫名其妙编码。最简单的办法就是真正的置换索引存储在数组中，但如果你不想这样做，出于某种原因（例如过大），可以以各种方式对其进行编码。天下没有免费的午餐，虽然，因为有关于如何简单这可能是信息理论极限。无论如何，你可以从仰视的“编码排列”例如像本文工作得到一些想法

下面是我自己虚构的语言的伪代码：

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的映射，去与费雪耶茨在其他的答案中提到

如果你不关心约1：1映射，你只需要所有所得到的值的是从给定的序列（具有重复的可能性），则可以使用随机函数具有指定范围内。

例如，在C ++，可以以下面的方式使用兰特（） - 

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

因此，对于你例如，

result = rand() % 8 + 10

将产生10至17之间的整数。

可以拟合多项式以所选择的序列;我想这就是你的同事向您展示。它不会节省空间相比，只是想起了置换，但。

您可以使用分组密码和异或折叠来生成前 n 个整数的排列，如下所示 我之前的回答.

这不是可以在不存储原始函数的结果某处返回的值。推理：

您随机数生成器告诉你，从原来的顺序返回这些值：5日，11日，3日

所以，你跳过前四个值，返回5日，跳过另一个5，返回11日...现在你怎么返回第三没有地方保存呢？

您可以与正在创建一个列表，并追加你跳过所有值，但声音很别扭，可能不值得努力摆脱最近的事情。此外，这将是在洗牌算法返回一个非常大的，然后一个很小的值（在这种情况下，你会最值要有效避免复制到列表中，第一，）的情况下很慢。

我休息我的情况。

如f(x) => x + 9开始于1

由f(x) => n - 1 + x描述你的输入，或者更一般x。

您链接到其描述了一种功能r(x)另一个问题其映射x到一个混洗值，0 <= r(x) <= m。

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

有关小m，你也应该能够通过试错的时候采取国防部m+1如果你不想编写自己的发电机，然后生成m+1不同的值，以找到一个标准的随机数生成器的种子。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top