1

I want to generate a list of floats of size M, where each item in the list is greater than the other proceeding items i.e. Descending order. and the sum of the list must sum to 1. and for the same M magnitude can I generate more than one list that obey to the given constraints.

I'm thinking of an equation in the following form:

Xi+1 = compute([Xi,Xi-1...X0], M, Random)

But I am not able to figure out the extent of this function. Thank you in advance.

adnanmuttaleb
  • 3,388
  • 1
  • 29
  • 46
  • 2
    Before coding, perhaps you first should try to do the mathematics behind this. How should the *i*-th element of such list look like? – Willem Van Onsem Oct 02 '18 at 19:23
  • 7
    generate a list with descending order, compute sum, and divide each element by the sum. – Jean-François Fabre Oct 02 '18 at 19:23
  • of-course @WillemVanOnsem – adnanmuttaleb Oct 02 '18 at 19:24
  • Note: [Float point arithmetic only has a certain amount of precision.](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) It's unlikely to sum to exactly `1`, it may be `0.99999...` or `1.0000001...`. If your floats only go up to a certain decimal place, it's better to compute this using integers instead and see if it sums to some large number like `100000` for 5 decimals. – Spencer Wieczorek Oct 02 '18 at 19:24
  • I think solution of @Jean-FrançoisFabre will solve my problem – adnanmuttaleb Oct 02 '18 at 19:26
  • It might not. precision matters while summing up the values again to 1. – mad_ Oct 02 '18 at 19:30

3 Answers3

5

okay, so let's pick 10 random numbers from 0 to 10, and sort them. Then compute sum and rebuild a new list with each element divided by this sum:

import random

# create a non-normalized ascending list of numbers
lst = sorted(random.uniform(0,10) for _ in range(10))
# compute the sum
temp_sum = sum(lst)
# now divide each member by the sum to normalize the list
lst = [i/temp_sum for i in lst]

print(lst,sum(lst))

one output could be:

[0.0340212528820301, 0.05665995400192079, 0.07733861892990018,
 0.07752841352220373, 0.08556431469182045, 0.11628857362899164,      
0.11706017358757258, 0.12523809404875455, 0.14272942597136748, 
0.16757117873543856] 1.0

The sum could be not exactly 1 because of floating point inaccuracy, but will be very close.

Jean-François Fabre
  • 137,073
  • 23
  • 153
  • 219
  • 1
    You can make this slightly more precise by using randint with a large enough upper bound and then doing the division. This way, the sum itself is exact. – Olivier Melançon Oct 02 '18 at 19:44
  • with a large lower bound too then. – Jean-François Fabre Oct 02 '18 at 19:45
  • If you use 2^64 -1 (or 2^32 -1 in 32 bits), the result will be mathematically identical, but normalization will be more precise. This happens to the expense of performance, because Python has to handle division by a long int though. – Olivier Melançon Oct 02 '18 at 19:48
  • @OlivierMelançon this seems nice. You should post your answer. I don't think I'm entitled to "steal" that :) – Jean-François Fabre Oct 02 '18 at 20:11
  • This is a really concise answer! Just a quick note: to generate a list in *descending* order (per the [OP](https://stackoverflow.com/q/52615056/4057186)), you only need to change `sorted(random.uniform(0,10) for _ in range(10))` to `list(reversed(sorted(random.uniform(0,10) for _ in range(10))))` – edesz Jan 20 '21 at 19:15
  • thanks. But why not just `sorted([random.uniform(0,10) for _ in range(10)],reverse=True)` ? and quoting op _"where each item in the list is greater than the other proceeding items i.e. Descending order"_. So increasing values all right, no reverse... – Jean-François Fabre Jan 20 '21 at 19:45
2

If you want something that is mathematically predictable...

def makeDescendingUnitArray(length: int):
    if (not isinstance(length, int)) or (length < 1):
        raise ValueError("Array Length must be an int with a value of at least 1")
    if length == 1:
        return [1]
    else:
        constant = 1
        output = list()
        for x in range(length - 2):
            constant /= 2
            output.append(constant)
        return output + [2*constant/3, constant/3]

for arrayLength in range(1, 10):
    array = makeDescendingUnitArray(arrayLength)
    print(array)

Produces the following arrays...

[1]
[0.6666666666666666, 0.3333333333333333]
[0.5, 0.3333333333333333, 0.16666666666666666]
[0.5, 0.25, 0.16666666666666666, 0.08333333333333333]
[0.5, 0.25, 0.125, 0.08333333333333333, 0.041666666666666664]
[0.5, 0.25, 0.125, 0.0625, 0.041666666666666664, 0.020833333333333332]
[0.5, 0.25, 0.125, 0.0625, 0.03125, 0.020833333333333332, 0.010416666666666666]
[0.5, 0.25, 0.125, 0.0625, 0.03125, 0.015625, 0.010416666666666666, 0.005208333333333333]
[0.5, 0.25, 0.125, 0.0625, 0.03125, 0.015625, 0.0078125, 0.005208333333333333, 0.0026041666666666665]
David Culbreth
  • 2,610
  • 16
  • 26
1

If you want a mathematically predictable one-liner, then there's this... (loop to show you what it looks like)

for length in range(1, 10):
    array = [2*x/(length * (length + 1)) for x in range(length,0,-1)]
    print(sum(array), array)

This produces the following output. Note that this is just as susceptible to the floating point rounding errors as all of the other algorithms. There are some better and some worse algorithms, but at some point, they'll all have some error.

Sum: 1.0 Array: [1.0]
Sum: 1.0 Array: [0.6666666666666666, 0.3333333333333333]
Sum: 0.9999999999999999 Array: [0.5, 0.3333333333333333, 0.16666666666666666]
Sum: 0.9999999999999999 Array: [0.4, 0.3, 0.2, 0.1]
Sum: 1.0 Array: [0.3333333333333333, 0.26666666666666666, 0.2, 0.13333333333333333, 0.06666666666666667]
Sum: 0.9999999999999998 Array: [0.2857142857142857, 0.23809523809523808, 0.19047619047619047, 0.14285714285714285, 0.09523809523809523, 0.047619047619047616]
Sum: 1.0 Array: [0.25, 0.21428571428571427, 0.17857142857142858, 0.14285714285714285, 0.10714285714285714, 0.07142857142857142, 0.03571428571428571]
Sum: 1.0 Array: [0.2222222222222222, 0.19444444444444445, 0.16666666666666666, 0.1388888888888889, 0.1111111111111111, 0.08333333333333333, 0.05555555555555555, 0.027777777777777776]
Sum: 0.9999999999999999 Array: [0.2, 0.17777777777777778, 0.15555555555555556, 0.13333333333333333, 0.1111111111111111, 0.08888888888888889, 0.06666666666666667, 0.044444444444444446, 0.022222222222222223]
David Culbreth
  • 2,610
  • 16
  • 26