生成排序后的随机整数而不进行排序?O(n)

因此,你要问的是,以这种方式生成的数字是否会均匀分布。

您正在生成一个系列:

Y _J = ∑ _i=0 ^J (十)

哪里 A _我 . x _我

_我 指数分布(具有任何固定平均值)。那么,如果x _{我 J}

尽管如此,生成指数x还是相当容易的 _我 价值观

一个例子是:

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) .

参考: Generating Sorted Lists of Random Numbers . 本文还有其他(更快的)算法。

当然,这会生成浮点数。均匀分布 整数 sum 高于 sum/RANGE X[I]*RANGE/sum

A. uniform distribution 有上限和下限。如果你使用你提出的方法,而你的delta恰好被选得足够大,以至于在你生成所有的数字之前,你会遇到上界,那么你的算法下一步会做什么?

Poisson distribution ,这是以给定平均频率发生的随机事件之间的间隔时间分布。

如果数字范围为1到1000,并且必须使用其中的100个数字,则增量必须至少为10,否则无法达到1000标记。我们来做些工作,在实践中证明一下吧。。。

在一个均匀分布的随机选择中,任何给定数字的概率为100/1000,例如1/10——没有冲击,以此为基础。

假设你开始使用一个增量,这个增量只有10。

获得数字1的几率是1/10——看起来不错。

第一种情况是增量为3,第二种情况是连续命中3个增量为1,第三种情况是增量为1后接2,第四种情况是增量为2后接1。

很快,前几个数字比直接随机数的概率更大。

这可以通过改变delta值来改变,所以分数都是不同的,但我不相信你能找到产生相同几率的delta。

Alok's answer 和 Dan Dyer's comment 指出使用 exponential distribution

因此,问题中代码示例的新版本将是:

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 exponential distribution random number generator (非常有用!)。在这里,它的平均值为1.0,但是由于脚本对序列中的最后一个数字进行了标准化,所以平均值本身并不重要。

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

Q:得到的整数分布是否与从均匀分布的概率密度函数生成100个随机整数相同?

答:每个三角洲将均匀分布。中心极限定理告诉我们,大量偏差之和的分布(因为它们具有有限的均值和方差)将趋向于正态分布。因此,你序列中的后一个偏差将 不 要均匀分布。

因此,简短的回答是“不”。恐怕我不能给出一个简单的答案 解决方案

这个 reference Alok's answer 这很有趣。它给出了一种生成均匀顺序统计信息的算法,该统计信息不是通过加法而是通过逐次乘法生成的:

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

其中RAND在[0,1]上是一致的。这样,您不必在最后进行规范化,事实上甚至不必将数字存储在数组中;您可以将其用作迭代器。

The Exponential distribution: theory, methods and applications By N. Balakrishnan, Asit P. Basu 第22页给出了该算法的另一种推导,并将其归功于Malmquist(1950)。

你可以在两个关卡内完成;

在第二步中,将随机数归一化,使其在边界内

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