寻找一种算法吐出数序列中一个（伪）随机顺序 [英] Looking for an algorithm to spit out a sequence of numbers in a (pseudo) random order

问题描述

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

Suppose I have a sequence of numbers: {n, n+1, n+2, ... n + m}

如果没有提前储存时间的数字我想创建一个函数f（），它给出的序列{1,2,3，... M}会吐出随机原设定（或至少是伪随机的）命令。

Without storing the numbers ahead of time I want to create a function f(), which given the sequence {1,2,3,...m} will spit out the original set in a random (or at least pseudo random) order.

有关假设我的序列的例子是{10，11，12，13，14，15，16，17}

For example assume my sequence is {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

在过去一个点一个同事给我看，这是能够做到这一点的数学算法，但我已经忘记其他比它几乎存在关于它的一切。我记得你必须有顺序提前，并且从它是在函数中使用的顺序一些常量。而对于那些想知道，我已经失去了伤心地与同事联系。

At one point in the past a co-worker showed me a mathematical algorithm that was able to do this, but I have since forgotten almost everything about it other than it existed. I remember that you had to have the sequence in advance, and generate some constants from the sequence which were used in the function. And for those wondering, I have sadly lost contact with that co-worker.

这<一href="http://stackoverflow.com/questions/693880/create-random-number-sequence-with-no-repeats">question's答案看起来接近我想要的，但我不知道，如果答案让我提前时间限制的输出到一个特定的顺序。

This question's answers looks close to what I want, but I am not sure if the answers allow me to constrain the output to a specific sequence ahead of time.

---

编辑：

要澄清一点，我不希望存储原始序列，或者打乱顺序。我想要生成函数f（）从原始序列

To clarify a little more I don't want to store the original sequence, or the shuffled sequence. I want to generate a function f() from the original sequence.

什么是令人沮丧的是，我已经看到了这一点，我只是不记得有足够的了解它再次找到它与谷歌的。

What is frustrating is that I have seen this, I just cannot remember enough about it to find it again with google.

费雪耶茨算法是伟大的置换或洗牌甲板，但它不是我所期待的。

The Fisher-Yates algorithm is great for permuting or shuffling a deck, but it is not what I am looking for.

推荐答案

有一个简单的函数，它生成的 [0..m-1] A置换为鉴于 M 。只需选择一个号码 K ，互素 M 让 F（I）=（ K * I）模m 。这总是生成一个置换（关于 0℃不重复; = I＆其中，M ）。它的工作原理更好，如果 K 比 M 。

There is a simple function that generates a permutation of [0..m-1] for a given m. Just pick a number k, relatively prime to m and let f(i)=(k*i) mod m. This always generates a permutation (no repeats on 0<=i<m). It works better if k is larger than m.

例如，M = 20，令k = 137（Python的code，％表示模）：

For example, m=20, let k=137 (Python code, % means modulo):

 >>> [(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，没有关于其统计性质的保证。

This is a very simple PRNG, no guarantees about its statistical properties.

这篇关于寻找一种算法吐出数序列中一个（伪）随机顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！