Re: Using a list as a variable
- To: mathgroup at smc.vnet.net
- Subject: [mg67120] Re: [mg67069] Using a list as a variable
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Fri, 9 Jun 2006 01:10:03 -0400 (EDT)
- References: <200606080854.EAA12414@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Bonny Banerjee wrote:
> I would like to use a list (or set) as a variable. I am working on the
> Subset-Sum problem. Given a set S of integers, the goal is to find a subset
> of S (say Q) whose elements add to a given integer x. This is how I would
> like to define the function:
>
> SubsetSum(S, x) := {Q such that Q is a subset of S and sum of the elements
> of Q is x}
>
> In Mathematica functional programming language, this would look like:
>
> SubsetSum[S_, x_] := Reduce[Q \[Element] Subsets[S] && Sum[Q,
> {i,1,Length[Q]}]==x, Q, Reals]
>
> Now when I try to evaluate SubsetSum[{1, 3, 5, 2, 7, 100, 6}, 101], the
> output is as follows:
>
> Reduce : : naqs :
> \[Exists]{Q} Q is not a quantified system of equations and
> inequalities. More ...
>
> Out[365]= Reduce[Q, False, Q, Reals]
>
>
> I guess, Mathematica is not being able to understand from my statement that
> the variable Q is not an atom but a list. But it should since I stated that
> Q is an element of the power set of S.
>
> Note that I know how to write a function for Subset-Sum using a Module. But
> I am interested in functional programming, similar to the format shown
> above.
>
> Any help would be appreciated.
>
> Thanks much,
> Bonny.
Even if you find a way to express this quantification, it will not be of
much use. You'd be forming all subsets and this will quickly blow up
your memory.
Better to use the standard approaches of explicit backtracking or
writing a system of equations with variables constrained to be 0 or 1.
For an example of the former approach you might have a look at
http://forums.wolfram.com/mathgroup/archive/2003/Apr/msg00409.html
The latter can be done quite readily as below.
subsetSum[ll_List,x_] := Module[{vars},
vars = Array[Unique[],Length[ll]];
((vars /. First[FindInstance[Flatten[
{vars.ll == x, Map[0<=#<=1&,vars]}], vars, Integers]]) * ll) /.
0->Sequence[]
]
Example:
subsetSum[{5,7,11,17}, 12]
Out[30]= {5, 7}
A more challenging example, from the URL above, would be to take
reciprocals of squares from 1/4 to 1/40^2 and see if we can sum to 1/2.
In[35]:= vec = Table[1/n^2, {n, 2, 40}];
In[36]:= InputForm[Timing[subsetSum[vec, 1/2]]]
Out[36]//InputForm=
{1.8961190000000003,
{1/4,1/9,1/16,1/25,1/49,1/144,1/225,1/400,1/784,1/1225}}
If you really want this in more "functional" style (you don't), then:
subsetSum2[ll_List,x_] :=
(((# /. First[FindInstance[Flatten[
{#.ll==x,Map[0<=#<=1&,#]}], #, Integers]]) * ll) /.
0->Sequence[])& [Array[Unique[],Length[ll]]]
I'm not sure which worries me more, that there are people who have
learned to read this kind of stuff, or that there are people who have
learned to write it.
Daniel Lichtblau
Wolfram Research
- References:
- Using a list as a variable
- From: "Bonny Banerjee" <banerjee@cse.ohio-state.edu>
- Using a list as a variable