2

These are the lines I'm using, it produces a list of the possible combinations of the sum to an integer typed in and then states the amount of combinations.

import itertools

val = int(input())
r = range(val)[1:]
res = []    
for i in range(len(r)+1):
    res += [list(x) for x in itertools.combinations(r, i) if sum(list(x)) == val]    
print("Solution : %s " % res)
print("Combinations : %s" % len(res))
Gary Dinmore
  • 47
  • 4

2 Answers2

1

It looks like you are calculating every single possible combination, and then keeping only the combinations that satisfy your sum condition. The combination pool it is searching through grows at a rate 2^(n-1) which you can see by commenting out the condition part:

import itertools
import time

startTime = time.time()

val = 21
r = range(val)[1:]
res = []    
for i in range(len(r)+1):
    res += [list(x) for x in itertools.combinations(r, i)]# if sum(list(x)) == val]    
#print("Solution : %s " % res)
print("Combinations : %s" % len(res))

print(time.time() - startTime, 'seconds')

Try this:

def a(lst, target, with_replacement=False):
    def _a(idx, l, r, t, w):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u if w else (u + 1), l + [lst[u]], r, t, w)
        return r
    return _a(0, [], [], target, with_replacement)

val = 50
s = range(1, val)
solutions = a(s, val)
print(solutions)
print(len(solutions))

which is modified from code by thefourtheye: Finding Combinations to the provided Sum value

timing it: original code:

val = 24, t = 6.5917372703552253 seconds
val = 25, t = 13.705767631530762 seconds
val = 26, t = 27.934977531433105 seconds
val = 50, t = 459889248.39282094 seconds

above method:

val = 24, t = 0.0084612369537353 seconds
val = 25, t = 0.0069310665130615 seconds
val = 26, t = 0.0085859298706054 seconds
val = 50, t = 0.4947729110717773 seconds
Zulfiqaar
  • 603
  • 1
  • 6
  • 12
  • What I'm trying to do is return every combination of numbers that are less than n and do not repeat. So for input 6, the return would be [1,5], [1,2,3], [2,4]. My code returns these fine and then states the number of combinations, in this case, 3, but when I input values larger than 25 the return takes much longer, I understand the return is exponential but the results of 141 combinations shouldn't take as long as it is. – Gary Dinmore Oct 20 '17 at 16:49
  • What your code is doing is finding every single combination including invalid ones, and then chucking away everything except the few you want to keep. So for a sum value of 25, thats 16,777,216 combinations your code searches through to find the valid ones. And all these combinations double with every increment to your value. I edited my answer with a working solution that works far faster at these scales – Zulfiqaar Oct 20 '17 at 17:10
  • Oh I see now, that is much faster. Thank you – Gary Dinmore Oct 20 '17 at 17:51
  • Zulfiqaar: You shouldn't blindly copy code. The `with_replacement` keyword argument isn't actually _used_ for anything in the `a()` or `_a()` functions (except being passed from the former to the latter so it can ignore it, too). – martineau Oct 20 '17 at 18:34
1

There are probably many ways to improve the speed. I tried (and noticed that it makes a big difference) a simple one: getting rid of the repeated conversions between generators and lists. Here's your code, modified:

import time
import itertools

#val = int(input("val:"))
#r = range(val)[1:]

def simple_time_func(func):
    def wrapper(*args, **kwargs):
        start = time.time()
        r = func(*args, **kwargs)
        print("{} took {:.3f} seconds.".format(func.__name__, time.time() - start))
        return r
    return wrapper

@simple_time_func
def original(val, r):
    res = list()
    for i in range(len(r) + 1):
        res += [list(x) for x in itertools.combinations(r, i) if sum(list(x)) == val]
    return res

@simple_time_func
def improved0(val, r):
    res = list()
    for i in range(len(r) + 1):
        res += [x for x in itertools.combinations(r, i) if sum(x) == val]
    return res


for val in range(21, 28):
    r = range(val)[1:]
    print("\nval: {}".format(val))
    for func in (original, improved0):
        res = func(val, r)
        #print("    Solution : %s " % res)
        #print("    Combinations : %s" % len(res))

Notes:

  • I took the expensive portion (the for loop) and encapsulated it in a function (original) in order to time it
  • I placed the improved loop in another function (called it improved0)
  • The rest of the code (unfortunately, also the most of it) is simply for performance testing

Output:

(py35x64_test) c:\Work\Dev\StackOverflow\q46853086>"c:\Work\Dev\VEnvs\py35x64_test\Scripts\python.exe" a.py

val: 21
original took 0.573 seconds.
improved0 took 0.325 seconds.

val: 22
original took 1.185 seconds.
improved0 took 0.633 seconds.

val: 23
original took 2.388 seconds.
improved0 took 1.300 seconds.

val: 24
original took 4.880 seconds.
improved0 took 2.609 seconds.

val: 25
original took 9.796 seconds.
improved0 took 5.243 seconds.

val: 26
original took 19.701 seconds.
improved0 took 10.489 seconds.

val: 27
original took 39.314 seconds.
improved0 took 21.559 seconds.

As the output shows, this apparently insignificant change almost cuts the time in half.
Next step consists of real optimization (as the computational complexity still looks exponential), regarding efficient usage of mathematical and programming skills, to improve the speed even more (unfortunately I'm running out of time).

CristiFati
  • 38,250
  • 9
  • 50
  • 87