Re: Using a list as a variable

*To*: mathgroup at smc.vnet.net*Subject*: [mg67082] Re: Using a list as a variable*From*: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>*Date*: Fri, 9 Jun 2006 01:06:52 -0400 (EDT)*Organization*: The Open University, Milton Keynes, UK*References*: <e68qc9$d2i$1@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. > > Hi Bonny, What about the following function (see In[1])? You wanted functional programming, you've got it :-)] In[1]:= subsetSum[S_,x_]:=Extract[#,Position[Plus@@@#,x]]&@Rest@Subsets@Union@S In[2]:= subsetSum[{1,3,5,2,7,100,6},101] Out[2]= {{1,100}} In[3]:= mySet=Range[3] Out[3]= {1,2,3} In[4]:= subsetSum[mySet,3] Out[4]= {{3},{1,2}} In[5]:= subsetSum[mySet,12] Out[5]= {} In[6]:= subsetSum[mySet,0] Out[6]= {} In[7]:= mySet=Table[Random[Integer,{1,4}],{10}] Out[7]= {2,1,4,2,1,3,2,3,2,3} In[8]:= Subsets[mySet]//Length Out[8]= 1024 In[9]:= subsetSum[mySet,6] Out[9]= {{2,4},{1,2,3}} By the way, I might be pessimistic but I do not believe that Reduce is capable of doing what you are looking for. Best regards, Jean-Marc