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)
- need a function for sums of subsets