Re: Puzzle

*To*: mathgroup at smc.vnet.net*Subject*: [mg2284] Re: Puzzle*From*: wagner at goober.cs.colorado.edu (Dave Wagner)*Date*: Mon, 23 Oct 1995 12:39:28 -0400*Organization*: University of Colorado, Boulder

In article <DGMpFD.ICL at wri.com>, Will Self <wself at viking.emcmt.edu> wrote: >Here's a nice puzzle. Find the four numbers in the following sequence >which total 100: {6, 44, 30, 15, 24, 12, 33, 23, 18}. It would seem that >there might be a nice way to do this with Mathematica. Any takers? > >Will Self >Billings, Montana > This is a classic dynamic programming problem. As is typical, it's easy to come up with an incredibly inefficient recursive solution. To see if k numbers out of the list sum to n, do the following for each element x of the list: Drop x from the list, and if k-1 numbers in the resulting list sum to n-x, then x is one of the numbers you are looking for. This solution strategy is incredibly inefficient (exponential time complexity, I believe) because identical recursive calls are made many times. (Analogous to a recursive calculation of the fibonacci numbers, but much harder to analyze for this particular problem.) Now you can make this very inefficient solution much more efficient (polynomial time, I believe, but don't quote me on that!) by caching the results of the recursive calls. Here's a Mathematica interpretation of this: (* sumto[seq, k, n] returns a list of k numbers from seq that sum to n, if possible; otherwise it returns Null. *) In[1]:= Clear[sumto] sumto[seq_, k_, n_] := sumto[seq, k, n] = Module[{i, tmp}, Do[ tmp = sumto[Drop[seq, {i}], k-1, n-seq[[i]]]; If[tmp =!= Null, Return[Append[tmp, seq[[i]]]]], {i, Length[seq]} ] ] sumto[_, 0, 0] := {} (* this indicates success *) sumto[___] := Null (* this indicates failure *) Here's an example: In[5]:= sumto[{1,2,3}, 2, 5] Out[5]= {3, 2} There are now a bunch of cached values for sumto: In[6]:= ?sumto Global`sumto sumto[{}, -1, -1] = Null sumto[{2}, 0, 1] = Null sumto[{3}, 0, 2] = Null sumto[{1, 3}, 1, 3] = {3} sumto[{2, 3}, 1, 4] = Null sumto[{1, 2, 3}, 2, 5] = {3, 2} sumto[_, 0, 0] := {} sumto[seq_, k_, n_] := sumto[seq, k, n] = Module[{i, tmp}, Do[tmp = sumto[Drop[seq, {i}], k - 1, n - seq[[i]]]; If[tmp =!= Null, Return[Append[tmp, seq[[i]]]]]\ , {i, Length[seq]}]] sumto[___] := Null Here is your original problem: In[7]:= nums = {6, 44, 30, 15, 24, 12, 33, 23, 18}; In[8]:= sumto[nums, 4, 100] Out[8]= {18, 23, 15, 44} The timing of this question could not have been better! People interested in a detailed treatment of dynamic programming using Mathematica should refer to the article "Dynamic Programming", by yours truly, which just appeared in The Mathematica Journal vol. 5 iss. 4. Dave Wagner Principia Consulting (303) 786-8371 dbwagner at princon.com http://www.princon.com/princon