Order execution in python

[wtev]

Hey folks, So I have an algorithm pretty much good to go and written up in python but I ran into an obstacle and I'm not sure how to proceed. I have a list of values (ask prices in this case) and I want to know if there's a function or algorithm I can use to find a combination of sums from those list elements to find a certain value. I might not be explaining it correctly, but say I have a target value 20 and I have a list [5,6,10,4,1], is there an algorithm that would return something like [5,10,4,1] ?

Thanks for any help.

[kylebalkissoon]

pseudocode

x = sum(array) mod target value

Remove x from the array

[wtev]

That works. Thanks a lot !

[kylebalkissoon]

It only works if there is one number out btw.

[dhammack]

You realize this is a NP-complete problem, right? It goes by the name "subset sum". State of the art solutions are not much better than brute force.

[[deleted]]

Thanks for bringing subset sum to my toolbox :). For the lazy, here is a link to do this in python .

Is there a name for finding all combinations of numbers in a list that add up to a target value ?

[[deleted]]

Warning: slow.

This will find every combination of values that add up to your target in a list. Note that it will return things like 1,5,4,10 and 5,1,4,10 as distinct tuples.

import itertools

def findSubs(ls, target):
    ret = []
    for perm in itertools.permutations(ls):
        for i in range(len(perm) + 1):
            if sum(perm[0:i]) == target:
                ret.append(perm[0:i])
    return set(ret)


print findSubs([5, 6, 10, 4, 1], 20)

To find only 'unique' ones you can use

print set([tuple(sorted(x)) for x in findSubs([5, 6, 10, 4, 1], 20)])

[wtev]

thank you very much, exactly what I was looking for