Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

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: [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



  • Prev by Date: Re: Re: Re: Colored Tick Labels?
  • Next by Date: Re: Or in a Select question
  • Previous by thread: Re: Using a list as a variable
  • Next by thread: Re: Using a list as a variable