不使用排序生成有序随机整数？O(n)

Question

我刚看到一个Code Golf问题，关于生成一个有序的100个随机整数列表。然而，萌生在我的脑海中的想法是，你可以生成一个正数delta列表，然后只需将它们加到运行总数中：

deltas: 1 3 2  7  2
ints:   1 4 6 13 15

事实上，您可以使用浮点数，然后归一化以适合某个上限并四舍五入，但效果是相同的。虽然这不会使代码更短，但没有排序步骤肯定会更快。但我真正无法掌握的是：生成的整数分布是否与从均匀分布概率密度函数中生成100个随机整数的分布相同？编辑：一个示例脚本：

import random,sys
running = 0
max = 1000
deltas = [random.random() for i in range(0,11)]
floats = []
for d in deltas:
    running += d
    floats.append(running)
upper = floats.pop()
ints = [int(round(f/upper*max)) for f in floats]
print(ints)

输出结果（公平的骰子掷出）为：

[24, 71, 133, 261, 308, 347, 499, 543, 722, 852]

更新：Alok的回答和Dan Dyer的评论指出，使用指数分布来生成增量将会得到一个整数的均匀分布。

- Phil H

---

这不会是统一的。请参考我的答案或Rupert Nash的答案。 - Alok Singhal

Answer 1

所以您想知道以这种方式生成的数字是否会均匀分布。

您正在生成一个序列：

y_j = ∑_i=0^j ( x_i / A )

其中A是所有x_i的总和。x_i是（正的）增量列表。

只有当x_i呈指数分布时，才能这样做（具有任何固定平均值）。因此，如果x_i是均匀分布的，则产生的y_j将不是均匀分布的。

话虽如此，生成指数x_i值相当容易。

一个例子是：

sum := 0
for I = 1 to N do:
    X[I] = sum = sum - ln(RAND)
sum = sum - ln(RAND)
for I = 1 to N do:
    X[I] = X[I]/sum

你将会获得在范围[0, 1)内排序的随机数。

参考文献: 生成排序的随机数列表。该论文还有其他（更快速的）算法。

当然，这会生成浮点数。如果要得到均匀分布的整数，则可以在最后一步中将上述代码中的sum替换为sum/RANGE（即右侧变为X[I]*RANGE/sum），然后将数字四舍五入到最近的整数。

- Alok Singhal

---

太好了！这总是以前做过的！我不理解代码行 X[I] = sum = sum - ln(RAND) 为什么要减去？顺便说一下，也许可以将您的方程式格式化为 HTML，如下所示：y_j = ∑_i=0^j ( x_i / A )。 - Phil H

谢谢，符号让我有点困惑，我忘记了RAND会小于1。在Python之外的语言中，我会将其放入代码中，但它有自己的指数变量函数。顶级的东西。 - Phil H

当我尝试使用RANGE/sum更改来实现这个时，最后一项总是等于RANGE。 - efritz

@efritz，我刚试过了，没有看到这种行为。你确定你在按照示例代码做吗？例如，在第一个循环之后有一个 sum = sum - ln(RAND)。 - Alok Singhal

这是一份未被付费墙所限制的论文版本：http://repository.cmu.edu/cgi/viewcontent.cgi?article=3483&context=compsci - Thomas Ahle

Answer 2

一种均匀分布具有上限和下限。如果您使用提议的方法，并且您选择的增量足够大，以至于在生成所有数字之前遇到上限，那么您的算法会怎么做？

话虽如此，您可能希望调查泊松分布，这是发生随机事件的时间间隔的分布，其发生频率具有给定的平均值。

- Greg Hewgill

---

我想他已经回答过这个问题了，是吗？如果你正在使用浮点数，你需要从最大 delta 大小的倍数中计算出最大的上限。然后在最后，你需要进行归一化，以便数据范围与上限完全匹配。 - Benj

是的，虽然您会生成一个最终要丢弃的额外数字，以便最后一个数字不总是上限。为了清晰起见，添加了代码示例。 - Phil H

泊松分布很有趣，也可能是这里需要的，但它给出的是在给定时间内发生一定数量事件的概率，而不是单个事件之间时间的概率分布。有什么想法可以修改它来得到这个？ - Phil H

@Phil H：在事件之间使用指数分布。 - Dan Dyer

@Dan：谢谢你，也感谢Alok在他的回答中指出了这一点。 - Phil H

Answer 3

如果你选择1到1000的数字范围，并且必须使用其中的100个数字，那么最小的增量必须为10，否则无法达到1000。下面演示一些工作来说明它的实际应用...

在均匀分布的随机选择中，任何给定数字的概率是100/1000，例如1/10 - 没有惊喜，将其作为基础。

假设您开始使用一个增量，这个增量只是10。

获得数字1的几率是1/10 - 看起来很好。 获得数字2的几率是1/10 + (1/10 * 1/10)（因为您可能会连续命中两个1的增量，或者仅仅第一个增量是2。） 获得数字3的几率是1/10 + (1/10 * 1/10 * 1/10) + (1/10 * 1/10) + (1/10 * 1/10)

第一种情况是增量为3，第二种情况是连续命中3个1的增量，第三种情况是增量为1后跟着2，第四种情况是增量为2后跟着1。

出于我的手指打字的考虑，我们不会生成命中5的组合。

立即可以看出，前几个数字的百分比比直接随机更高。

通过改变增量值，可以改变这种情况，使得所有分数都不同，但我不认为您能找到一个产生相同几率的增量。

给出一个类比可能更好理解，如果将您的增量视为6，然后运行两次，就相当于掷2个骰子 - 每个增量是独立的，但您知道7被选中的机会比2大。

- Andrew

---

你的意思是不能使用均匀分布来生成delta值。没错，这就是泊松分布在这种情况下的优势所在。 - Greg Hewgill

Answer 4

"Alok的回答"和"Dan Dyer的评论"指出，使用指数分布来计算增量会得到整数的均匀分布。因此，问题中代码示例的新版本应为：

import random,sys
running = 0
max = 1000
deltas = [random.expovariate(1.0) for i in range(0,11)]
floats = []
for d in deltas:
    running += d
    floats.append(running)
upper = floats.pop()
ints = [int(round(f/upper*max)) for f in floats]
print(ints)

请注意使用了random.expovariate(1.0)，这是一个Python指数分布的随机数生成器（非常有用！）。 在这里，它以1.0的平均值被调用，但由于该脚本针对序列中的最后一个数字进行归一化，因此平均值本身并不重要。

输出（公正骰子投掷）：

[11, 43, 148, 212, 249, 458, 539, 725, 779, 871]

- Phil H

Answer 5

我认为这两者非常相似，但由于归一化，极端值会有所不同。例如，在1到100之间随机选择100个数字可能都是1。然而，使用该系统创建的100个数字可能具有0.01的增量，但当您对它们进行归一化时，您将把它们缩放到1-100的范围内，这意味着您永远不会得到一组非常低的数字。

- Benj

---

我只需生成一个最终的增量来得到我的上限，然后将其丢弃。因此，第101个数字可以非常大，从而实现您所描述的情况。 - Phil H

好的，假设你想要得到1到100之间的数字，但是你随机生成了一个上限（比如说67）。这意味着你的数字范围会自然而然地倾向于在1到67之间均匀分布，而不是在1到100之间均匀分布，其中67恰好是最大的数字。这样看起来就不太一样了... - Benj

Answer 6

参考文献（1979年）在Alok的回答中很有趣。它提供了一种通过连续乘法而不是加法生成均匀顺序统计量的算法：

max = 1.
for i = N downto 1 do
   out[i] = max = max * RAND^(1/i)

其中RAND在[0,1)上是均匀分布的。这样你就不必在最后进行归一化，实际上甚至不必将数字存储在数组中；你可以将其用作迭代器。

指数分布：理论、方法和应用 作者：N. Balakrishnan, Asit P. Basu在第22页给出了另一个推导该算法的方法，并将其归功于Malmquist（1950年）。

- Stanislav

---

起初，我认为"Malmquist"与天文学中被命名为"Malmquist偏差"的那个人是同一人，但事实证明并非如此。因此，至少有两位著名的Malmquist统计学家 :-) - Alok Singhal

这如何避免规范化？对于介于1和255之间的整数，您的代码只会产生逐渐变小且全部小于1的值。如果有一个最大整数被提供，那么集合必须一次性生成，否则平均值等会发生变化。 - Phil H

从255开始并使用Int（*）量化输出。 加1以获得[1,255]。 - Stanislav

Answer 7

问：生成100个随机整数的分布是否与从均匀分布概率密度函数生成100个随机整数的分布相同？

答：每个增量将是均匀分布的。中心极限定理告诉我们，由于它们具有有限的平均值和方差，大量这样的偏差之和的分布将趋向于正态分布。因此，您序列中后面的偏差将不会均匀分布。

所以简短的答案是“不”。恐怕我今天没有时间做代数运算，无法给出简单的解决方案！

- Rupert Nash

---

你的意思是，如果我有一个在 [1..n] 范围内的均匀（未排序）的随机数序列，那么它们之间的差值不会在 [0..n-1] 范围内均匀分布？ - Andreas Brinck

我的意思是均匀分布的差异总和（即增量）不会像所需的那样均匀分布。你所说的也是显然的：因为你提到的未排序数字平均而言将有一半的差异为负数。 - Rupert Nash

@Andreas：不，它们将具有三角分布：http://en.wikipedia.org/wiki/Triangular_distribution - Ofri Raviv

Answer 8

你可以分两步来完成：

第一步，生成0到（MAX_RAND/n）之间的增量；

第二步，将随机数归一化为在范围内。

仍然是O(n)，具有良好的引用局部性。

- Will

---

嗯，再次阅读原帖后，我认为他已经达到了这一点。 - Will