How to randomly generate decreasing numbers in Python?

Question

I'm wondering if there's a way to generate decreasing numbers within a certain range? I want to program to keep outputting until it reaches 0, and the highest number in the range must be positive.

For example, if the range is (0, 100), this could be a possible output: 96 57 43 23 9 0

Sorry for the confusion from my original post

Answer 1

I would generate a list of n random numbers then sort them highest to lowest.

Answer 2

Few thing have to be noted. The algorithm which starts in X > 0 and in each step takes a random number from (0,X) and replaces X with it is no good. Why? Because ( assuming random behaves properly ) expected value in each step is in the middle of interval (0,X). This implies that the sequence of these numbers is expected to converge to 0 as fast as (1/2)^N. And indeed it can be easily seen that majority of numbers are near 0, even for enormous inital value. This means that the distribution of these numbers is not uniform, which is a desired property most of the time.

This is a major drawback, even though the complexity of generating Nth number is O(N) and ( what is more important ) memory usage is O(1).

The other solution is to just take N random numbers and sort them. This is not bad, although complexity of this algorithm is O(N log(N)) ( or rather the same as the complexity of underlying sorting algorithm ), which can be reduced to O(N) if we put elements in order instead of sorting, but memory usage is O(N) - we have to remember all elements. However these numbers will be uniformly distributed, which is a great advantage!

Following the idea in the paper "Generating sorted lists of random numbers" by Jon Louis Bentley here's the algorithm which probably is the most optimal one ( at least known to me ) and produces uniformly distributed numbers:

import math
import random

def generate( min = 0, max = 10, number = 100 ):
    start = 0
    for i in xrange( number, 0, -1 ):
        start = start + math.log( random.random( ) ) / i
        next = math.exp( start ) * ( max - min ) + min
        yield next

for number in generate( ):
    print number

Note that complexity of this algorithm is still O(N) ( which I doubt can get lower ) but memory usage is O(1) and these numbers are uniformly distributed in interval (min,max), which is not that obvious, but true. The only drawback is that we have to know how many numbers we want to generate before starting.

Also have a look at this thread:

Generating sorted random ints without the sort? O(n)

Might be useful.