按排序顺序生成随机数 [英] Generating random number in sorted order
问题描述
我想按排序顺序生成随机数。
我写了以下代码：
I want to generate random number in sorted order. I wrote below code:
void CreateSortedNode(pNode head)
{
int size = 10, last = 0;
pNode temp;
while(size-- > 0) {
temp = (pnode)malloc(sizeof(struct node));
last += (rand()%10);
temp->data = last;//randomly generate number in sorted order
list_add(temp);
}
}
期望的数字以升序或降序生成：即{2，5，9，23，45，68}
Expecting number will be generated in increased or decreased order: i.e {2, 5, 9, 23, 45, 68 }
int main()
{
int size = 10, last = 0;
while(size-- > 0) {
last += (rand()%10);
printf("%4d",last);
}
return 0;
}
还有更好的主意吗？
推荐答案
在没有有关样本大小或样本Universe的任何信息的情况下，不容易知道以下内容是否有趣但无关紧要或没有解决方案，但是由于无论如何它都是有趣的，所以这里
Without any information about sample size or sample universe, it's not easy to know if the following is interesting but irrelevant or a solution, but since it is in any case interesting, here goes.
问题：
在 O（ 1）空间，从有序集 S n 的无偏有序随机样本>大小 N ：< S 1 ，S 2 ，… S < sub> N > ，这样样本中的元素与有序集合中的元素的顺序相同。
In O(1) space, produce an unbiased ordered random sample of size n from an ordered set S of size N: <S1,S2,…SN>, such that the elements in the sample are in the same order as the elements in the ordered set.
解决方案：
-
概率为
n / | S |，请执行以下操作：
-
add
S 1到示例。
add
S1to the sample.
减量 n
从 S S 1 >
Remove S1 from S
重复步骤1和2，每次使用新的第一个元素（和大小）为 S 直到 n 为0，此时样本将具有所需的元素数量。
Repeat steps 1 and 2, each time with the new first element (and size) of S until n is 0, at which point the sample will have the desired number of elements.
python中的解决方案：
from random import randrange
# select n random integers in order from range(N)
def sample(n, N):
# insist that 0 <= n <= N
for i in range(N):
if randrange(N - i) < n:
yield i
n -= 1
if n <= 0:
break
解决方案的问题：
花费 O（N） 时间。我们真的想花 O（n）的时间，因为 n 可能比<$ c小得多c $ c> N 。另一方面，我们想保留 O（1）的空间，以防 n 也很
It takes O(N) time. We'd really like to take O(n) time, since n is likely to be much smaller than N. On the other hand, we'd like to retain the O(1) space, in case n is also quite large.
更好的解决方案（仅概述）
（以下为改编自Jeffrey Scott Visser于1987年发表的论文《顺序随机采样的高效算法》，这得益于Visser博士的慷慨支持，可从ACM数字图书馆免费获得。 ittc.ku.edu/~jsv/Papers/catalog/5SAMPLING_HISTOGRAMS.html rel = nofollow>维瑟博士的出版物页面。。有关详细信息，请阅读该论文。）
(The following is adapted from a 1987 paper by Jeffrey Scott Visser, "An Efficient Algorithm for Sequential Random Sampling", which thanks to the generosity of Dr. Visser is available freely from the ACM digital library. See Dr. Visser's publications page.. Please read the paper for the details.)
而不是像上面的python代码那样增加 i 并选择一个随机数，如果能够根据到某种分布，这就是 i 将递增而不产生任何元素的次数。我们所需要的就是分布（这显然取决于 n 和 N 的当前值。）
Instead of incrementing i and selecting a random number, as in the above python code, it would be cool if we could generate a random number according to some distribution which would be the number of times that i will be incremented without any element being yielded. All we need is the distribution (which will obviously depend on the current values of n and N.)
当然，我们可以从算法检查中得出精确的分布。但是，这并没有多大帮助，因为生成的公式需要大量时间才能准确计算，最终结果仍然是 O（N）。
Of course, we can derive the distribution precisely from an examination of the algorithm. That doesn't help much, though, because the resulting formula requires a lot of time to compute accurately, and the end result is still O(N).
但是，我们不一定总是要精确地计算它。假设我们有一些容易计算的合理近似值，该近似值始终低估了概率（结果是有时无法做出预测）。如果这种近似有效，我们可以使用它；如果没有，我们将需要退回到精确的计算。如果这种情况很少发生，我们平均可以实现 O（n）。实际上，维瑟博士的论文展示了如何做到这一点。 （使用代码。）
However, we don't always have to compute it accurately. Suppose we have some easily computable reasonably good approximation which consistently underestimates the probabilities (with the consequence that it will sometimes not make a prediction). If that approximation works, we can use it; if not, we'll need to fallback to the accurate computation. If that happens sufficiently rarely, we might be able to achieve O(n) on the average. And indeed, Dr. Visser's paper shows how to do this. (With code.)
这篇关于按排序顺序生成随机数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
