0
$\begingroup$

More out of curiosity than anything else. I know you can always generate a list of random numbers and then sort it, but I was wondering if there exists a (pseudo)random number generator whose output is already in sorted order? I found this, but it and everything else I found only generates integer lists. Is there an equivalent for floats and without worrying about repetition?

$\endgroup$
7
  • $\begingroup$ From what distribution? The uniform distribution on [0,1]? Something else? $\endgroup$
    – D.W.
    May 10 at 3:51
  • 1
    $\begingroup$ What's wrong with sorting? Generally questions that have the form "I want an algorithm to solve problem P, but not algorithm A, I want some other algorithm" are not very useful (it gives little idea why you have rejected algorithm A; if I suggest algorithm B, maybe you'll reject that one too; and there are many ways to build an algorithm that is effectively equivalent to A but not obviously so). It is better to identify some specific criteria or requirements that sorting doesn't satisfy (perhaps you want O(n) runtime? a streaming algorithm with O(1) memory? something else?). $\endgroup$
    – D.W.
    May 10 at 3:51
  • $\begingroup$ en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/… $\endgroup$
    – D.W.
    May 10 at 3:52
  • $\begingroup$ (everything [found] generates integer lists assuming non-negative values only and sorted order to mean non descending, take the "head sums" of the list, add lower limit of desired range and scale by ratio of final sum and range.) $\endgroup$
    – greybeard
    May 10 at 5:17
  • $\begingroup$ @D.W. The question is more out of interest than practicality. It seems like an interesting problem to directly generate a sorted list of random floats - I'm wondering if it's possible as it seems like it would be tricky to have a truly random sampling whilst also guaranteeing that future samples are larger. In terms of use case, if you are generating many long lists of random integers and sorting them for use in some application, it's not a stretch to say that the sorting could become the bottleneck in this case. $\endgroup$
    – Sas2450
    May 11 at 0:25

1 Answer 1

1
$\begingroup$

You haven't answered the question about what distribution, so I will assume you want the uniform distribution on [0,1].

Yes, this can be done. However, I doubt that the result will be better in practice than just generating $n$ numbers uniformly at random and sorting them.

Based on the order statistics of the uniform distribution, the distribution of the smallest of $n$ numbers from the uniform distribution is known: it has a Beta$(1,n)$ distribution. Also, it is known how to sample from such a distribution.

So, there is a simple algorithm: sample the first number $x_1$ from the sorted sequence, by generating a random sample from Beta$(1,n)$. Then, sample the second number $x_2$, by letting $x_2 = x_1 + d_2/(1-x_1)$ where $d_2$ is sampled from Beta$(1,n-1)$, and $x_3 = x_2 + d_3/(1-x_1-x_2)$ where $d_3$ is sampled from Beta$(1,n-2)$, and so on.

Why does this work? Well, obviously $x_1$ has the right distribution. Also, the numbers $x_2,\dots,x_n$ can be obtained by sampling uniformly at random from $[x_1,1]$ and sorting, so we can generate them recursively using the same algorithm. Finally, unwinding the recursion gives the above algorithm.

$\endgroup$
2
  • $\begingroup$ Amazing thanks! Can you tell me why you doubt the result will be better in practice than sorting? $\endgroup$
    – Sas2450
    May 11 at 0:45
  • $\begingroup$ @Sas2450, sorting is simple and quite efficient in practice, whereas sampling from a Beta distribution looks more complex to me. $\endgroup$
    – D.W.
    May 11 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.