Recursion for Integer Partitioning using numbers only once in Python is slow

Question

I am trying to calculate the number of possible combinations to add up to a single value using every number just once in Python 2.7.

For example for 7 this would be 6+1, 5+2, 4+3, 4+2+1 --> 4 possible combinations

I managed to forge this into a recursive function that does the math right

import time

counter_list = []

def start(n):
    tic=time.time()
    recursive_step(range(1, n), n)
    toc=time.time()
    print(toc - tic)
    return len(counter_list)

def recursive_step(numbers, target, summe=0):

    if summe == target:
        counter_list.append(1)
    if summe >= target:
        return

    for i in xrange(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        recursive_step(remaining, target, summe + n)

if __name__ == "__main__":
    print(start(7))

Unfortunally it becomes very slow when the numbers become bigger. Following are some numbers I meassured on my machine.

~~~ 40 ~~~
time in seconds:        0.0789999961853
possible combinations:  1112
~~~ 50 ~~~
time in seconds:        0.40299987793
possible combinations:  3657
~~~ 60 ~~~
time in seconds:        1.51200008392
possible combinations:  10879
~~~ 70 ~~~
time in seconds:        5.41400003433
possible combinations:  29926
~~~ 80 ~~~
time in seconds:        18.388999939
possible combinations:  77311
~~~ 90 ~~~
time in seconds:        54.5920000076
possible combinations:  189585

I have looked into dynamic programming principles. But I could not get it to work on that Problem. Any advice on how I can improve that script would be greatly appreciated

These are not the only possible ways to build `7`---> `6,1-->3,3,1-->1,2,3,1... 5,2-->3,2,2-->1,2,2,2... 4,3-->2,2,3-->1,1,2,2...` there many ways not just 4. Tell exactly how to get only those 4 combinations — Ch3steR, Mar 28 '20 at 09:06
This is a difficult problem, so don't feel bad about it being slow. Here is what an efficient solution looks like: https://stackoverflow.com/a/44209393/2482744 — Alex Hall, Mar 28 '20 at 09:11
Note to commenters: this is "distinct partitions" rather than "partitions". That's partition function Q rather than P. — Paul Hankin, Mar 28 '20 at 11:15

score 7 · Accepted Answer · answered Mar 28 '20 at 11:14

Reference on this sequence: http://oeis.org/A000009

You can think of the problem of partitioning n into distinct parts as a coin change problem with (single) coins of values 1 to n. (Or one less than this, since it seems you're disallowing the partition of n as the single number n).

You can count solutions by adapting a standard coin-change dynamic programming solution.

def Q(n):
    A = [1] + [0] * n
    for i in range(1, n+1):
        for j in range(n, i-1, -1):
            A[j] += A[j-i]
    return A[n] - 1

print(Q(500))

You can understand this program by noting that after k iterations of the outer loop, A[i] contains the number of ways of partitioning i with the distinct elements from 1..k. And that the number of ways of partitioning i with distinct elements from 1..k+1 is the number of ways of partitioning i with distinct elements from 1..k plus the number of ways of partitioning i-k-1 with elements from 1..k.

This runs in O(n^2) time, but it's fast for small cases (eg: partitions of 500 here, takes 0.033s on my machine).

This works! And it is literally so fast I cant even meassure how much faster it is then my solution! Seems like magic. I will have to spend some time trying to understand why it is such a gigantic difference. Thank you very much for your solution and your great explanation. — Maximilian Jesch, Mar 28 '20 at 12:23

Recursion for Integer Partitioning using numbers only once in Python is slow

1 Answers1