MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Mathematics Packages
  • Next by Date: Re: .NET/Link and two-dimensional strings
  • Previous by thread: Re: Using a list as a variable
  • Next by thread: rules for using functions as basis vectors