Re: need a function for sums of subsets
- To: mathgroup at smc.vnet.net
- Subject: [mg33040] Re: [mg33001] need a function for sums of subsets
- From: Ken Levasseur <Kenneth_Levasseur at uml.edu>
- Date: Wed, 27 Feb 2002 00:47:56 -0500 (EST)
- References: <200202250631.BAA09782@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Mark:
You didn't say how you would order the subsets, so "first" isn't
defined. Also, since finding any list is essentially the knapsack
problem it would seem to me that efficiency will be a problem.
Ken Levasseur
Math. Sciences.
UMass Lowell
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
- References:
- need a function for sums of subsets
- From: mwganson@hotmail.com (Mark Ganson)
- need a function for sums of subsets