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
– Ch3steR, Commented Mar 28, 2020 at 9:06
This is a difficult problem, so don't feel bad about it being slow. Here is what an efficient solution looks like: stackoverflow.com/a/44209393/2482744 — Alex Hall
– Alex Hall, Commented Mar 28, 2020 at 9:11
Note to commenters: this is "distinct partitions" rather than "partitions". That's partition function Q rather than P. — Paul Hankin
– Paul Hankin, Commented Mar 28, 2020 at 11:15

Paul Hankin · Accepted Answer · 2020-03-28 11:14:57Z

7

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).

answered Mar 28, 2020 at 11:14

Paul Hankin

58.8k11 gold badges99 silver badges125 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Maximilian Jesch Over a year ago

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.

Collectives™ on Stack Overflow

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

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related