Re: need a function for sums of subsets

*To*: mathgroup at smc.vnet.net*Subject*: [mg33023] Re: [mg33001] need a function for sums of subsets*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Tue, 26 Feb 2002 04:35:10 -0500 (EST)*References*: <200202250631.BAA09782@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Mark Ganson wrote: > > Hello, > > I need a function that will find the first subset of a list that will > sum up to a given value. > > For example, if I have a list of rationals: > > myrationals = {1/2, 1/3, 1/4, 1/8, 3/10, 12/79, 13/38} > > I would like a function that will return the first subset of > myrationals that sums up to a given parameter. > > We can call the function "findsum". It would work like so: > > In: findsum[myrationals, 3/4] > Out: {1/2, 1/4} > > It would be nice also, but not essential, to be able to use another > list as the second parameter and have the function return a list of > lists. > > Example: > > In: findsum[myrationals, {3/4, 3/8}] > Out: {{1/2, 1/4}, {1/4, 1/8}} > > I need something really fast and memory efficient because my lists > tend to be quite large (up to 100 elements). > > Many thanks, > > Mark Ganson This is an example of a "subset sum" problem, and those are, if I recall correctly, NP-complete. Hence you will want to investigate possibly using integer programming methods and/or heuristic techniques. Also it may not be feasible to insist on getting a "first" such subset (assuming you have a definite ordering in mind). One heuristic method that sometimes works to get such subsets is to use lattice reduction. I am not sure of the state of the art in this, but below are examples indicating one approach, using your set of rationals. myrationals = {1/2, 1/3, 1/4, 1/8, 3/10, 12/79, 13/38}; Form a lattice with an identity matrix on the left and your rationals, rescaled by some large integer, in the last column. lattice1 = Transpose[Append[ IdentityMatrix[Length[myrationals]], 10^10*myrationals]]; Now augment by a row with zeros up to the last column, and the target value, negated and likewise rescaled, in the last position. lattice2 = Append[lattice1, Append[Table[0,{Length[myrationals]}], -10^10*3/4]] We will reduce this lattice. If we get a row with a zero in the last column and only zeros and ones before it, those ones indicate which rationals sum to the target. In[433]:= InputForm[LatticeReduce[lattice2]] Out[433]//InputForm= {{1, 0, 1, 0, 0, 0, 0, 0}, {-2, 0, 1, 0, 0, 0, 0, 0}, {-1, 0, 0, -2, 0, 0, 0, 0}, {1, 3, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, -5, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 19, 0}, {0, 0, 0, 0, 0, 79, 0, 0}, {0, 1, -1, -1, 1, -3, -6, 250000000/4503}} The first row tells us that the first and third rationals summed to 3/4. We will try another example, this time using four of the list elements. lattice3 = Append[lattice1, Append[Table[0,{Length[myrationals]}], -10^10*(1/3+1/4+3/10+13/38)]]; In[437]:= InputForm[LatticeReduce[lattice3]] Out[437]//InputForm= {{-1, 0, 2, 0, 0, 0, 0, 0}, {0, 0, 1, -2, 0, 0, 0, 0}, {0, 1, 1, 0, 1, 0, 1, 0}, {-2, 2, -1, 0, -1, 0, -1, 0}, {3, 1, 1, 0, -4, 0, 1, 0}, {-10, -7, -5, -2, -4, 0, 15, 0}, {5, 3, 3, 2, 2, 79, -7, 0}, {3, 2, 2, 1, 2, -3, -5, 250000000/4503}} The third row gives a solution. Note that one can get small nonsolution rows such as row 1 above just from having "small" relations between subsets of list elements. This in turn might mess up an actual solution. For example, row 3 above might instead have been row 3 - row 1, or {1,1,-1,0,1,0,1,0}. This does not give a solution. For a large problem it might be far from obvious how to combine rows to repair such a deficiency. So this method is only heuristic in that it might fail to find solutions even when they exist. Fortunately such "bad" rows are usually larger in Euclidean measure than actual solutions, and moreover while lattice reduction is not guaranteed to get smallest rows, it usually does. Daniel Lichtblau Wolfram Research

**References**:**need a function for sums of subsets***From:*mwganson@hotmail.com (Mark Ganson)