Code optimization - amount of combinations

Question

There is a number C given (C is an integer) and there is given a list of numbers (let's call it N, all the numbers in list N are integers). My task is to find the amount of possibilities to represent C.

For example:

input:

C = 4

N = [1, 2]

output:

Because:

4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 2 + 2

My code is working pretty well for small numbers. However I have no idea how can I optimize it so it will work for bigger integers too. Any help will be appreciated!

There is my code:

import numpy
import itertools
def amount(C):
    N = numpy.array(input().strip().split(" "),int)
    N = list(N)
    N = sorted(N)
    while C < max(N):
        N.remove(max(N))
    res = []
    for i in range(1, C):
        for j in list(itertools.combinations_with_replacement(N, i)):
            res.append(sum(list(j)))
    m = 0
    for z in range (0, len(res)):
        if res[z] == C:
            m += 1
    if N[0] == 1:
        return m + 1 
    else:
        return m

There's really no need for numpy here. If anything, it's going to slow you down. And you immediately turn it into a `list` anyway. That makes no sense. — juanpa.arrivillaga, Dec 27 '16 at 22:16
You seem to want to count partitions: see https://en.wikipedia.org/wiki/Partition_(number_theory). — Bill Bell, Dec 27 '16 at 22:25
You can benchmark your code against npartitions in http://docs.sympy.org/dev/_modules/sympy/ntheory/partitions_.html. — Bill Bell, Dec 27 '16 at 22:29
@juanpa.arrivillaga that's right! I will change it in a moment. Thanks. — Hendrra, Dec 27 '16 at 22:59
@BillBell Thank you. I think that might help. However I don't know how can I add my list of integers which sums are to represent C. — Hendrra, Dec 27 '16 at 23:00

score 2 · Accepted Answer · answered Dec 27 '16 at 23:53

2

Complexity of your algorithm is O(len(a)^С). To solve this task more efficiently, use dynamic programming ideas.

Assume dp[i][j] equals to number of partitions of i using terms a[0], a[1], ..., a[j]. Array a shouldn't contain duplicates. This solution runs in O(C * len(a)^2) time.

def amount(c):
    a = list(set(map(int, input().split())))

    dp = [[0 for _ in range(len(a))] for __ in range(c + 1)]
    dp[0][0] = 1

    for i in range(c):
        for j in range(len(a)):
            for k in range(j, len(a)):
                if i + a[k] <= c:
                    dp[i + a[k]][k] += dp[i][j]

    return sum(dp[c])

answered Dec 27 '16 at 23:53

Andreikkaa

297
1
7

That runs very fast! Thanks for the help. – Hendrra Dec 28 '16 at 09:40
And that's right - my array contained a lot of duplicates. Can you explain how does the last "if" work, please? – Hendrra Dec 28 '16 at 09:43
@Hendrra this is a kind of bounds checking. This `if` statement doesn't affect on solution at all. – Andreikkaa Dec 28 '16 at 14:17
ok, thanks! Can I ask for the explanation of the first line containing dp? I think that I miss the point what it really is. – Hendrra Dec 28 '16 at 14:26
@Hendrra On the 4th line there's 2D-list generation. You can read about this trick [here](http://stackoverflow.com/questions/6667201/how-to-define-two-dimensional-array-in-python). – Andreikkaa Dec 28 '16 at 15:20
Thanks a lot! That's a really nice trick I must say. One more question - what is dp[c]? How can we jump from a 2D list to 1D list? – Hendrra Dec 28 '16 at 17:11
@Hendrra I think you mean the `return sum(dp[c])` statement. The `sum` function returns sum of values in given container. In our case, the container is the last layer of array `dp[c]`. This is the answer on our task. You can read about `sum` [here](http://stackoverflow.com/questions/4362586/sum-a-list-of-numbers-in-python). – Andreikkaa Dec 28 '16 at 22:01

score 0 · Answer 2 · answered Dec 27 '16 at 23:17

please check this first : https://en.wikipedia.org/wiki/Combinatorics
also this https://en.wikipedia.org/wiki/Number_theory
if i were you , i would divide the c on the n[i] first and check the c is not prim number from your example : 4/1 = [4] =>integer count 1
4/2 = [2] => integer counter became 2 then do partitioning the [2] to 1+1 if and only if 1 is in the set
what if you have 3 in the set [1,2,3] , 4/3 just subtract 4-3=1 if 1 is in the set , the counter increase and for bigger results i will do some partitioning based on the set

Thanks for all the links and a new idea. It's a nice solution (and it shows a lot of Maths)! I will consider it too. I think however that it might be a bit slower that one above. — Hendrra, Dec 28 '16 at 09:48

Code optimization - amount of combinations

2 Answers2