Partition number theory with Python

Question

Given an integer total calculate number of possible ways to represent total. Sum required is 5 while integers can be considered as [1,2,3]

The 5 ways to target sum are:

1 + 1 + 1 + 1 + 1 = 5

1 + 1 + 1 + 2 = 5

1 + 2 + 2 = 5

1 + 1 + 3 = 5

2 + 3 = 5

Input is 5, 3, where 3 is the range[1,2,3] to reach total 5

Output is 5

Check the documentation for Itertools (https://docs.python.org/3/library/itertools.html#itertools.combinations). You'll find combinations requires two arguments. — nick, Jan 08 '19 at 06:49
The error `TypeError: Required argument 'r' (pos 2) not found` can be self-understood. Where do you get stuck? — meW, Jan 08 '19 at 06:51
@RoadRunner not exactly. The solution from there will not result into the expected answer. I've checked it. — meW, Jan 08 '19 at 07:05
Possible duplicate of [Find all combinations of a list of numbers with a given sum](https://stackoverflow.com/questions/34517540/find-all-combinations-of-a-list-of-numbers-with-a-given-sum) — phimuemue, Jan 08 '19 at 19:39

score 0 · Answer 1 · answered Jan 08 '19 at 07:37

I don't think using combinations() will work here- the function returns combinations of the array you pass it, but does not create duplicates of any given element. You could get around this by using a variant combinations_with_replacement(), but even then you'll end up with an excess of invalid combinations, and for lengthy lists the runtime would become intractable.

Instead, consider a recursive solution like the following.

def reps(target, nums):
     res = []
     for i, v in enumerate(nums):
         if target - v > 0:
             res += [[v] + l for l in reps(target-v, nums[i:])]
         elif target - v == 0:
             res += [[v]]
     return res

Here I take a target sum and a list of numbers, and try subtracting out each number from the target. If the difference exactly equals 0, I add that last value to the list. If its great than zero, I keep attempting to add elements to the list by calling reps() with the new target value, and a subset of the original numbers which prevents permutations of the same answer. I combine all these, prepend the previously chosen value from the list, and continue in this fashion until a list of all combinations has been built.

The result for your example target=5 and nums=[1,2,3]-

[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1, 2, 2], [2, 3]]

@Tomothy32 that's because `range(10)` includes `0`, and there are infinitely many solutions with adding `0` after `0`. — Dillon Davis, Jan 08 '19 at 07:50

iz_ · Accepted Answer · 2019-03-28T01:09:00.563

-1

Because your question only requires the number of possibilities and not the possibilities themselves, this is one of the fastest ways to do it:

def partitions(n, m):
    if n <= 1:
        return 1
    if m > n:
        return partitions(n, n)

    total = 0
    for i in range(1, m + 1):
        total += partitions(n - i, i)

    return total

Here, n is the number you are trying to partition and m is the limit on the largest number. It handles even very large numbers very quickly:

In [1]: def partitions(n, m):
   ...:     if n <= 1:
   ...:         return 1
   ...:     if m > n:
   ...:         return(partitions(n, n))
   ...:
   ...:     total = 0
   ...:     for i in range(1, m + 1):
   ...:         total += partitions(n - i, i)
   ...:
   ...:     return total
   ...:

In [2]: partitions(5, 3)
Out[2]: 5

In [3]: partitions(10, 5)
Out[3]: 30

In [4]: partitions(50, 30)
Out[4]: 202139 # returned in less than a second

edited Mar 28 '19 at 01:09

answered Jan 08 '19 at 07:44

iz_

15,923
3
25
40

What if the range isn't `[1, m]` inclusive, but rather something like `[1, 3, 17]`. The original question didn't specify the numbers are necessarily consecutive. – Dillon Davis Jan 08 '19 at 07:53
@DillonDavis OP says input is 5, 3, output is 5. So that's what I assumed he needed. – iz_ Jan 08 '19 at 08:05
@Tomothy32 could you explain the program – Jan 08 '19 at 08:12
@Maws It's more of a mathematical algorithm than a program. I recommend you check out the article here. https://en.wikipedia.org/wiki/Partition_(number_theory) – iz_ Jan 08 '19 at 08:14

Partition number theory with Python

2 Answers2