devide int into lower whole ints

Question

I have a random int in the range of 30-60 which I get using randint(30,60). Let's say it's 40. I want to split this number in exactly 7 random whole ints. So for instance [5,5,5,5,5,5,10] is a valid result. But there are many possible solutions, like this one as well [6,6,6,6,6,6,4] or [4,2,9,13,8,1,3] ... I know there are many solutions but I am searching for a fast way to go through them. I am not trying to get every single solution but rather looking for a fast way to iterate over a lot of them in short time. One way to achieve it is to randomly pick a number (let's say in the range from 1-15) and save it to a list, then do a while loop until the sum is exactly 40. I tried that and it is not efficient at all. I think choosing a start value like [5,5,5,5,5,5,10] and altering the numbers in a precise way like "1st digit -2" and 3rd +2 to yield [3,5,7,5,5,5,10] would be a much faster solution. Does anyone know how to do that or has a good suggestion? Thanks. I prefer python 3.

Answer 1

A set of whole numbers that sum to a number n is called a partition of n; if order matters then it's called a composition.

Here's a reasonably fast way to produce random compositions.

import random

def random_partition(n, size):
    seq = []
    while size > 1:
        x = random.randint(1, 1 + n - size)
        seq.append(x)
        n -= x
        size -= 1
    seq.append(n)
    return seq

n = 40 
for _ in range(20):
    print(random_partition(n, 7))

typical output

[26, 2, 8, 1, 1, 1, 1]
[30, 2, 1, 3, 1, 1, 2]
[26, 5, 3, 1, 2, 2, 1]
[2, 25, 9, 1, 1, 1, 1]
[28, 2, 2, 2, 1, 2, 3]
[23, 1, 9, 3, 2, 1, 1]
[3, 26, 1, 7, 1, 1, 1]
[25, 1, 7, 1, 2, 1, 3]
[10, 8, 11, 5, 3, 1, 2]
[19, 16, 1, 1, 1, 1, 1]
[12, 23, 1, 1, 1, 1, 1]
[1, 14, 15, 7, 1, 1, 1]
[29, 5, 1, 1, 2, 1, 1]
[25, 1, 3, 3, 1, 2, 5]
[10, 12, 10, 4, 1, 2, 1]
[13, 4, 6, 14, 1, 1, 1]
[31, 3, 1, 1, 1, 1, 2]
[16, 11, 9, 1, 1, 1, 1]
[3, 26, 5, 3, 1, 1, 1]
[31, 2, 1, 2, 2, 1, 1]

We use 1 + n - size as the upper limit because the other size - 1 numbers are at least 1.

Here's a fairly efficient way to generate all partitions of a given integer. Note that these are ordered; you could use random.shuffle if you want to produce random compositions from these partitions.

We first print all partitions of 16 of size 5, and then we count the number of partitions of 40 of size 7 (= 2738).

This code was derived from an algorithm by Jerome Kelleher.

def partitionR(num, size):
    a = [0, num] + [0] * (num - 1)
    size -= 1
    k = 1
    while k > 0:
        x = a[k - 1] + 1
        y = a[k] - 1
        k -= 1
        while x <= y and k < size:
            a[k] = x
            y -= x
            k += 1
        a[k] = x + y
        if k == size:
            yield a[:k + 1]

for u in partitionR(16, 5):
    print(u)

print('- ' * 32)
print(sum(1 for _ in partitionR(40, 7)))

output

[1, 1, 1, 1, 12]
[1, 1, 1, 2, 11]
[1, 1, 1, 3, 10]
[1, 1, 1, 4, 9]
[1, 1, 1, 5, 8]
[1, 1, 1, 6, 7]
[1, 1, 2, 2, 10]
[1, 1, 2, 3, 9]
[1, 1, 2, 4, 8]
[1, 1, 2, 5, 7]
[1, 1, 2, 6, 6]
[1, 1, 3, 3, 8]
[1, 1, 3, 4, 7]
[1, 1, 3, 5, 6]
[1, 1, 4, 4, 6]
[1, 1, 4, 5, 5]
[1, 2, 2, 2, 9]
[1, 2, 2, 3, 8]
[1, 2, 2, 4, 7]
[1, 2, 2, 5, 6]
[1, 2, 3, 3, 7]
[1, 2, 3, 4, 6]
[1, 2, 3, 5, 5]
[1, 2, 4, 4, 5]
[1, 3, 3, 3, 6]
[1, 3, 3, 4, 5]
[1, 3, 4, 4, 4]
[2, 2, 2, 2, 8]
[2, 2, 2, 3, 7]
[2, 2, 2, 4, 6]
[2, 2, 2, 5, 5]
[2, 2, 3, 3, 6]
[2, 2, 3, 4, 5]
[2, 2, 4, 4, 4]
[2, 3, 3, 3, 5]
[2, 3, 3, 4, 4]
[3, 3, 3, 3, 4]
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
2738

Answer 2

If you only care about getting an arbitrary set of numbers that add up to your total rather than an exhaustive iteration over all combinations, the following should get you what you need.

def get_parts(total, num_parts=7, max_part=15):
    running_total = 0
    for i in range(num_parts - 1):
        remaining_total = total - running_total
        upper_limit = min(max_part, remaining_total - num_parts + 1 + i)
        # need to make sure there will be enough left
        lower_limit = max(1, remaining_total - max_part*(num_parts - i - 1))
        part = randint(lower_limit, upper_limit)
        running_total += part
        yield part
    yield total - running_total

>>> list(get_parts(40))
[2, 7, 10, 11, 1, 4, 5]

>>> list(get_parts(40))
[7, 13, 11, 6, 1, 1, 1]

>>> list(get_parts(50, 4))
[6, 14, 15, 15]

Of course, the items in each list above is not truly random and will favor larger numbers earlier in the list and smaller numbers later. You can feed these lists through random.shuffle() if you want more of an element of pseudorandomness.

Answer 3

From Python Integer Partitioning with given k partitions

def partitionfunc(n,k,l=1):
    '''n is the integer to partition, k is the length of partitions, l is the min partition element size'''
    if k < 1:
        raise StopIteration
    if k == 1:
        if n >= l:
            yield (n,)
        raise StopIteration
    for i in range(l,n//k+1):
        for result in partitionfunc(n-i,k-1,i):
            yield (i,)+result
list(partitionfunc(40,7))

Answer 4

You can do a simple iteration over all possible combinations of the first 6 values (where the sum does not exceed 40), and calculate the 7th value.

for a in range(41):
    for b in range(41-a):
        for c in range(41-(a+b)):
            for d in range(41-(a+b+c)):
                for e in range(41-(a+b+c+d)):
                    for f in range(41-(a+b+c+d+e)):
                        g = 40 - (a+b+c+d+e+f)
                        # Do what you need to do here

You can cut the amount of time required by the loop almost in half (according to tests using timeit) by precomputing the sums:

for a in range(41):
    for b in range(41-a):
        ab = a + b
        for c in range(41-ab):
            abc = ab + c
            for d in range(41-abc):
                abcd = abc + d
                for e in range(41-abcd):
                    abcde = abcd + e
                    for f in range(41-abcde):
                        g = 40 - (abcde + f)
                        # Do what you need to do here