Get all the methods to break 100% into certain number of parts?

Question

Being straight about the question, for a program I'm writing, I need to divide 100% into 5 parts. In my program, percentages incremented/decremented by 10%. So I can express my requirement in the following format.

$x + y + z + a + b = 10$

where, $ x, y, z, a, b \in \mathbb{Z}^{0+}$

Is there any way to get all possible values for x, y, z, a, b? I thought of derivatives but it did not work. If we can find one pattern which we can fill the 5 spaces so the sum is 10, we can take all permutations of that pattern so if there's a way to get all patterns, then I guess the problem can be solved.

Other than that, I have no idea to solve this. Any help is appreciated.

Answer 1

Here's an efficient recursive solution in Python. The runtime is linear in the amount of output generated, and the memory usage is just the length of one solution.

def ordered_partitions(prefix, k, n):
    if k == 1:
        prefix.append(n)
        yield prefix
        prefix.pop()
    else:
        for x in range(0, n + 1):
            prefix.append(x)
            yield from ordered_partitions(prefix, k - 1, n - x)
            prefix.pop()

The output of

for result in ordered_partitions([], 3, 5):
    print(*result, sep='+')

is:

0+0+5
0+1+4
0+2+3
0+3+2
0+4+1
0+5+0
1+0+4
1+1+3
1+2+2
1+3+1
1+4+0
2+0+3
2+1+2
2+2+1
2+3+0
3+0+2
3+1+1
3+2+0
4+0+1
4+1+0
5+0+0

Answer 2

The solutions to $x_1 + x_2 + \cdots + x_k = n$, with $n\geq 0$ and all $x_i$ positive integers, are called compositions of $n$ into $k$ parts. You can generate them recursively, by first deciding the last part $x_k$, say $x_k = i$ with $1 \leq i \leq n$, and then appending it to every composition of $n - i$ into $k-1$ parts. In Python, this might look like

def Compositions(n,k):
    if k==1:
        yield [n]
    elif n == 0:
        yield []
    else:
        for i in range(1,n):
            for comp in Compositions(n-i, k-1):
                yield comp + [i]

for c in Compositions(10,5):
    print(c)

giving output

[6, 1, 1, 1, 1]
[5, 2, 1, 1, 1]
[4, 3, 1, 1, 1]
[3, 4, 1, 1, 1]
[2, 5, 1, 1, 1]
[1, 6, 1, 1, 1]
[5, 1, 2, 1, 1]
(... and so on)

Answer 3

You could do it (inefficiently) by generating all possibilities and rejecting ones that don't fit your constraints. Each of the 5 variables can take 11 values, in 10% increments from 0% to 100%. In a nested loop, you can enumerate all $11^5$ possible combinations of 10%-interval values. Finally, discard any combinations that do not sum to 100%. This leaves all possible combinations of 5 values that sum to 100% and are also in 10% intervals.

Answer 4

If you didn't allow $0$, then you'd be asking for the number of partitions of $10$ into $5$ parts. Usually written $p_5(10).$ Since you're allowing $0$ as a part, you need:

$$p_5(10)+p_4(10)+p_3(10)+p_2(10)+p_1(10).$$

There is a recursion relation for $p_k(n)$ given here:

https://en.wikipedia.org/wiki/Partition_(number_theory)#Restricted_part_size_or_number_of_parts

which will let you quickly compute the numbers you need.