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
I would generate a list of n random numbers then sort them highest to lowest.
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.
like:
from random import random
min=0
max=10
oldval=1.
while True:
oldval=oldval*random()
randval=min+(max-min)*oldval
Here are a few alternatives. This should produce close to a chi-square distribution of values, with later values selected from a smaller range than earlier values:
import random
random_range = range(10)
numbers = [random.choice(random_range[:i]) for i in range(10, 0, -1)]
This can also be done with floats:
import random
max = 10.0
min = 0.0
desired = 100
step = (max - min) / desired
numbers = [random.random() * (max - (i * step)) for i in range(desired)]
Alternatively, selecting random values from a decreasing sliding window can provide a uniform distribution.
import random, numpy
max = 10.0
min = 0.0
desired = 100
step = float(min - max) / desired
window = 1.0
numbers = [x + (random.random() * window) - (window / 2.0) for x in numpy.arange(max, min, step)]
If a monotonically-decreasing list of numbers is required, then setting window <= step will provide one. Good luck!
Building on @brentlance's idea, this will work for any integer range, positive, negative, or both:
import random
random_decreasing_integers_from_range = (i for i in xrange(max, min - 1, -1) if random.random() > .5)
If you want to be able to specify the number of outputs, here's an attempt at it that at least attempts to keep the distribution across the range somewhat uniform:
import random
def random_decreasing_integers_from_range(min, max, num_outputs):
range_size = abs(max - min)
if range_size < num_outputs:
raise ValueError('Distance from min to max must be equal to or greater than num_outputs.')
output_count = 0
for iteration, value in enumerate(xrange(max, min - 1, -1)):
# if we only have enough values left to satisfy the number requested,
# yield value
if num_outputs - output_count == range_size - iteration + 1:
output_count += 1
yield value
# else yield value randomly, weighted by how far in to the range we are
# and how many values we have left to yield of the total requested
else:
ratio_consumed = float(iteration + 1) / range_size
ratio_yielded = float(output_count) / num_outputs
if random.random() < (1 - ratio_yielded) * ratio_consumed:
output_count += 1
yield value
# if we've yielded the requested number of values, stop
if output_count == num_outputs:
break
This works reasonably well, but it seems to break down when num_outputs isn't between about 10% and 25% of range_size. At the lower bound, favoring the middle of the range really shows through, while at the upper bound, the short circuit condition starts to cause the results to really favor the lower end of the range.
Thanks, everybody for your answers. But I found a solution to my own problem which I thought was quite simple, and I would like to share that with all of you.
import random
i = 1000000
while i > 0:
i = random.randint(0, i)
print i
This will give you decreasing random numbers in the range 0..1.
import random
def generate():
n = 1.0
while n:
n = random.random() * n
yield n
iterator = generate()
iterator.next()
Note that the function stops yielding numbers after a while as the numbers inevitably reach 0 given the limited precision of floating point numbers.
Not an expert in python...but here's the basic idea I have:
a=10000
for i in range(1,50):
b=random.randint(1,a)
print(b)
a=b
