生成没有排序的排序随机整数?在) [英] Generating sorted random ints without the sort? O(n)

问题描述

只是在查看有关 Alok的回答和 Dan Dyer的评论指出使用指数分布的增量将给出整数的均匀分布.

解决方案

因此，您要问以这种方式生成的数字是否要均匀分布.

您正在生成系列:

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)范围内排序.

参考:生成随机数排序列表.本文还具有其他(更快的)算法.

当然，这会生成浮点数.为使 integers 均匀分布，您可以在最后一步中用sum/RANGE替换上面的sum(即RHS变为X[I]*RANGE/sum，然后将数字四舍五入到最接近的整数). /p>

Just been looking at a code golf question about generating a sorted list of 100 random integers. What popped into my head, however, was the idea that you could generate instead a list of positive deltas, and just keep adding them to a running total, thus:

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

In fact, you would use floats, then normalise to fit some upper limit, and round, but the effect is the same.

Although it wouldn't make for shorter code, it would certainly be faster without the sort step. But the thing I have no real handle on is this: Would the resulting distribution of integers be the same as generating 100 random integers from a uniformly distributed probability density function?

Edit: A sample script:

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)

Whose output (fair dice roll) was:

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

UPDATE: Alok's answer and Dan Dyer's comment point out that using an exponential distribution for the deltas would give a uniform distribution of integers.

解决方案

So you are asking if the numbers generated in this way are going to be uniformly distributed.

You are generating a series:

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

where A is the sum of all x_i. x_i is the list of (positive) deltas.

This can be done iff x_i are exponentially distributed (with any fixed mean). So, if x_i are uniformly distributed, the resulting y_j will not be uniformly distributed.

Having said that, it's fairly easy to generate exponential x_i values.

One example would be:

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

and you will have your random numbers sorted in the range [0, 1).

Reference: Generating Sorted Lists of Random Numbers. The paper has other (faster) algorithms as well.

Of course, this generates floating-point numbers. For uniform distribution of integers, you can replace sum above by sum/RANGE in the last step (i.e., the R.H.S becomes X[I]*RANGE/sum, and then round the numbers to the nearest integer).

这篇关于生成没有排序的排序随机整数?在)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！