Re: need a function for sums of subsets
- To: mathgroup at smc.vnet.net
- Subject: [mg33012] Re: need a function for sums of subsets
- From: Jens-Peer Kuska <kuska at informatik.uni-leipzig.de>
- Date: Tue, 26 Feb 2002 04:34:52 -0500 (EST)
- Organization: Universitaet Leipzig
- References: <a5clm3$9gl$1@smc.vnet.net>
- Reply-to: kuska at informatik.uni-leipzig.de
- Sender: owner-wri-mathgroup at wolfram.com
Hi,
if you only need pairs
Clear[findsum]
findsum[lst_, val_Rational] :=
Catch[Outer[If[Plus[#1, #2] == val, Throw[{#1, #2}]] &, lst, lst]]
findsum[lst_, {val__Rational}] := findsum[lst, #] & /@ { val}
Regards
Jens
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