As Joe Wallis Joe Wallis suggests, you probably want:
As Joe Wallis suggests, you probably want:
As Joe Wallis suggests, you probably want:
As Joe Wallis suggests, you probably want:
for i in xrange(1, len(dataArray)+1):
for comb in itertools.combinations(dataArray, i):
if abs(sum(comb) - target) < tolerance:
yield comb
That way the caller can decide if one is sufficient or if all of them are needed.
As Joe Wallis suggests, you probably want:
for i in xrange(1, len(dataArray)+1):
for comb in itertools.combinations(dataArray, i):
if abs(sum(comb) - target) < tolerance:
yield comb
That way the caller can decide if one is sufficient or if all of them are needed.
In keeping the same algorithm, there's a bunch of extra work you're doing that's slowing you down. I am using the word slow loosely, since the one example you provided is still more or less instantaneous and the timings I performed were based on 100,000 runs.
Leave iterables alone
You wrap your combinations() call with list(). This means that you have to do actually create all the combinations up front, then iterate over them. But you never actually need all of them at once. You just need them one at a time. Changing your body to:
results = [list(comb) for comb in itertools.combinations(dataArray, i)
if target-tolerance < sum(map(float, comb)) < target+tolerance]
drops runtime from 2.64s to 2.45s. Furthermore, comb is going to be a tuple, so that's fine as is too:
results = [comb for comb in itertools.combinations(dataArray, i)
if target-tolerance < sum(map(float, comb)) < target+tolerance]
Down to 2.24s. Another 10%.
Building lists for no reason
Our numbers are already summable, no need to cast them to float first. You're making a whole bunch of extra lists that you're immediately discarding - just to be able to do a sum. But you can already do a sum:
results = [comb for comb in itertools.combinations(dataArray, i)
if target-tolerance < sum(comb) < target+tolerance]
That alone brings us down to 1.10s. An enormous savings.
Comparisons
One comparison is faster than two comparisons, so let's just do the one:
results = [comb for comb in itertools.combinations(dataArray, i)
if abs(sum(comb) - target) < tolerance]
Down to 1.04s.
What do you actually want
This doesn't yield all of the potential partial sums. It will yield some sums if any exist, and will return None otherwise - but it won't give you all of them. If you want all of them, you'll have to loop through all of the is. If you just want the first one, then this:
for i in xrange(1, len(dataArray)+1):
for comb in itertools.combinations(dataArray, i):
if abs(sum(comb) - target) < tolerance:
return comb
just got reduced to 0.67s.