What is the funtional-style replacement of this loop?

Question

I have the following loop:

import random
distribution = []
sum = 0
while True:
  item = random.randint(1, 8)
  if sum + item == 812:
    distribution.append(item)
    break
  elif sum + item > 812:
    distribution.append(812 - sum)
    break
  else:
    distribution.append(item)
    sum = sum + item

The idea here is to create a list with items where each item is a random number between 1 and 8 and the sum of items in the list has to be exactly 812. The challenge is, that the last item can randomly overshoot, so a simple stop condition won't do.

I'm racking my brain on how to express this functionally, but came up blank so far. Any ideas?

Answer 1

I am answering the title of this question:

What is the functional-style replacement of this loop?

def random_list(sum_rest):
    item = random.randint(1, min(8, sum_rest))
    return ([] if sum_rest - item == 0 else random_list(sum_rest - item)) + [item]

This solution is based on the improvement proposed by @DollarAkshay, once you get that, it is very straightforward: I am recursively calling random_list, but decreasing the sum_rest parameter by the item randomly chosen.

You get the list by calling

random_list(812)

Answer 2

One solution is to generate random numbers such that they do not cross 812. For example when your sum is 806 you can only generate numbers between [1, 6].

So you should change your random number generator to be

item = random.randint(1, min(8, 812 - sum))

Also your entire program becomes much shorter. Note do not use the variable name sum as it is an inbuilt function

import random
distribution = []
list_sum = 0
while list_sum < 812:
    item = random.randint(1, min(8, 812 - list_sum ))
    distribution.append(item)
    list_sum += item

Answer 3

this is exactly what your if statements do - just rewritten with min:

MAX = 812
distribution = []
s = 0
while s < MAX:
    item = min(MAX - s, random.randint(1, 8))
    distribution.append(item)
    s += item

note that this will slightly skew your distribution. the last number will be consistently smaller than the others... one way to hide that a little would be to shuffle the list afterwards.

in order to have a really uniform distribution you'd have to start over in case you overshoot...

Answer 4

An answer that's similar to yours

import random
distribution = []
lsum = 0
while True:
    item = random.randint(1, 8)
    lsum = lsum + item
    distribution.append(item)
    if lsum > 812:
        lsum = lsum - item
        distribution.pop()
    if lsum == 812:
        break

Answer 5

Because you know the max value of items added, could you not just deterministically end with the last item as soon as you are within range of this max value at the end? In that case, you could do something like:

import random

def creat_random_list(total_sum, min_value=1, max_value=8):
    distribution = []
    current_sum = 0
    done = False
    while not done:
        if total_sum - current_sum <= max_value:
            new_item = total_sum - current_sum
            done = True
        else:
            new_item = random.randint(min_value, max_value)
        distribution.append(new_item)
        current_sum += new_item
    return distribution


random_numers = creat_random_list(total_sum=812)
print(f"sum {sum(random_numers)} of list {random_numers}")

Note that I have renamed your variable sum to current sum, because sum is an inbuilt function, so not a good variable name to pick

Result look like:

sum 812 of list [7, 5, 7, 4, 7, 7, 7, 1, 2, 6, 6, 4, 5, 3, 1, 4, 4, 2, 8, 7, 5, 5, 5, 5, 1, 1, 1, 4, 5, 5, 1, 1, 8, 8, 6, 5, 5, 5, 8, 2, 3, 7, 8, 6, 2, 6, 7, 4, 7, 7, 8, 7, 1, 4, 7, 2, 2, 6, 4, 4, 3, 4, 2, 6, 3, 3, 3, 4, 1, 3, 6, 6, 8, 5, 6, 3, 3, 7, 6, 8, 5, 3, 5, 4, 1, 7, 6, 5, 4, 1, 7, 1, 5, 1, 7, 3, 4, 2, 3, 3, 1, 4, 6, 5, 4, 1, 1, 1, 3, 7, 1, 3, 8, 8, 7, 4, 4, 8, 8, 8, 5, 6, 5, 6, 8, 5, 7, 2, 2, 8, 5, 1, 5, 4, 3, 2, 1, 1, 8, 8, 8, 8, 2, 1, 1, 4, 8, 4, 1, 2, 2, 2, 8, 5, 6, 5, 4, 1, 3, 4, 3, 3, 2, 2, 5, 7, 8, 1, 1, 8, 2, 7, 7, 2, 5, 1, 7, 7, 2, 3, 7, 7]

Answer 6

A disciplined (and practical) approach is to generate sequences, stopping when the sum is at least 812, and then restarting if the sum is above 812. This is called "rejection sampling". This guarantees that you are picking sequences fairly, and not skewing the randomness.

You expect approximately 1 in 8 of the samples to be good, so you expect to generate 8 samples before you find a good one.

import random

def seqsum(n):
    while True:
        S = 0
        s = []
        while S < n:
            s.append(random.randrange(8)+1)
            S += s[-1]
        if S == n:
            return s

for _ in range(10):
    print(seqsum(812))

Obviously this will be slower than skewing the last element or elements of the sequence to force the sum, but that's a trade-off for avoiding the skew.

Here's some code that prints out the distribution of the last element of the sequence, using this method, that of @hiro-protagonist and that of @DollarAkshay. It shows the frequencies of the numbers 1 to 8 in a sample of size 10000, printed as an array. You can see the heavy skew towards low numbers in those methods.

def seqhiro(n):
    S = 0
    s = []
    while S < n:
        s.append(min(812 - S, random.randint(1, 8)))
        S += s[-1]
    return s

def seqdollar(n):
    S = 0
    s = []
    while S < n:
        s.append(random.randint(1, min(8, 812 - S)))
        S += s[-1]
    return s

def sample(m):
    last = [0] * 9
    for _ in range(10000):
        s = m(812)
        last[s[-1]] += 1
    return last[1:]

print('rejection', sample(seqsum))
print('hiro', sample(seqhiro))
print('dollar', sample(seqdollar))

Output:

rejection [1234, 1308, 1280, 1178, 1246, 1247, 1257, 1250]
hiro [2226, 1904, 1727, 1319, 1077, 895, 560, 292]
dollar [5220, 1803, 938, 595, 475, 393, 319, 257]

Dollar Akshay's method produces 1 as the final number approximately 20 times more than 8, and hiro's method is better, but still 1 appears approximately 7.5 times more often than 8 as the final entry.

The method of this answer (rejection sampling) gives an approximately equal distribution for all final digits in this sample of 10000 runs.

Obviously it's possible to hide the skew of the fast methods, for example by shuffling the array before returning it, but the statistically correct method in this answer has nothing to hide.