CODEWITHSUNDEEP
pythonoptimizationpython-itertools
Hendrra
Hendrra

Reputation: 859

Code optimization - amount of combinations

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:

3

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

Upvotes: 1

Views: 328

Answers (2)

Andreikkaa
Andreikkaa

Reputation: 297

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

Upvotes: 2

Ahmed Mohamed
Ahmed Mohamed

Reputation: 1565

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

Upvotes: 0

Related Questions