1
|
5958 Views
|
11 Replies
|
2 Total Likes
View groups...
Share
GROUPS:

# Functional programming question ...

Posted 10 years ago
 I was recently challenged with the following puzzle ... Find the maximum subsequence sum of a list of integers. Here's a list ...(1, 2, -4, 1, 3, -2, 3, -1). The maximum subsequence sum is 5 = 1+3-2+3. One does not need to remember which subsequence yields the maximum, thus ties are not important Allegedly, the trick is to note that one can discard subsequences as soon as the sum goes down when processing linearly. How would one do this "functionally," without generating all subsequences first? After some years of practice I now think more about sets, and operations on them, rather than serial - procedural - operations on sequences. As this community will understand, often the set-based approach proves to be faster and more transparent. A non-procedural solution to this puzzle is eluding me. Thank you.
11 Replies
Sort By:
Posted 10 years ago
 I found this method to be much faster than some other methods... Does it also give the same results?
Posted 10 years ago
 Try this: ClearAll[MaxSubSeq] MaxSubSeq[x_List] := Module[{y}, y = Accumulate[x]; y = Ordering[x, -1][[1]]; Max[Accumulate[Reverse[Take[x, y]]]] ] the first line will calculate cumulative sum. Then we find the position of the maximum in that list. We take now only the original data up to that position we just found. We reverse the list, accumulate again, and find the max. I found this method to be much faster than some other methods...
Posted 10 years ago
 It is a well-known problem and many approaches are available on the web, look for Kadane's algorithm.Below is a functional style implementation, see this link for the derivation In[1]:= data = {1, 2, -4, 1, 3, -2, 3, -1}; f[{y_, z_}, x_] := {Max[{0, x + y}], Max[Max[0, x + y], z]} Last[Fold[f, {0, 0}, data]] Out[3]= 5 
Posted 10 years ago
 Thank you, Ilian! I suspected it had been studied.I really appreciate the "functional" implementation - a good example of how to serialize something in Mathematica.I'll now declare this thread CLOSED. I appreciate everyone's help.
Posted 10 years ago
 It is difficult to think of a solution that does not over-enumerate, except perhaps that no subsequence that begins with a negative number can be a candidate. So here is an exhaustive approach, which could be made much less understandable by more creative coding. ;-) In[1]:= data = {1, 2, -4, 1, 3, -2, 3, -1}; In[2]:= (* start and end of all possible subsequences *) indices = Flatten[Table[{i, j}, {i, Length[data]}, {j, i, Length[data]}], 1] Out[2]= {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {3, 3}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {4, 8}, {5, 5}, {5, 6}, {5, 7}, {5, 8}, {6, 6}, {6, 7}, {6, 8}, {7, 7}, {7, 8}, {8, 8}} In[3]:= subsequences = Take[data, #] & /@ indices Out[3]= {{1}, {1, 2}, {1, 2, -4}, {1, 2, -4, 1}, {1, 2, -4, 1, 3}, {1, 2, -4, 1, 3, -2}, {1, 2, -4, 1, 3, -2, 3}, {1, 2, -4, 1, 3, -2, 3, -1}, {2}, {2, -4}, {2, -4, 1}, {2, -4, 1, 3}, {2, -4, 1, 3, -2}, {2, -4, 1, 3, -2, 3}, {2, -4, 1, 3, -2, 3, -1}, {-4}, {-4, 1}, {-4, 1, 3}, {-4, 1, 3, -2}, {-4, 1, 3, -2, 3}, {-4, 1, 3, -2, 3, -1}, {1}, {1, 3}, {1, 3, -2}, {1, 3, -2, 3}, {1, 3, -2, 3, -1}, {3}, {3, -2}, {3, -2, 3}, {3, -2, 3, -1}, {-2}, {-2, 3}, {-2, 3, -1}, {3}, {3, -1}, {-1}} In[4]:= sums = Total /@ subsequences Out[4]= {1, 3, -1, 0, 3, 1, 4, 3, 2, -2, -1, 2, 0, 3, 2, -4, -3, 0, \ -2, 1, 0, 1, 4, 2, 5, 4, 3, 1, 4, 3, -2, 1, 0, 3, 2, -1} In[5]:= (* large to small *) orderingOfSums = Ordering[sums] // Reverse Out[5]= {25, 29, 26, 23, 7, 34, 30, 27, 14, 8, 5, 2, 35, 24, 15, 12, \ 9, 32, 28, 22, 20, 6, 1, 33, 21, 18, 13, 4, 36, 11, 3, 31, 19, 10, \ 17, 16} In[6]:= (* subsequence sum pairs *) subsequencesAndSums = {subsequences[[orderingOfSums]], sums[[orderingOfSums]]} // Transpose Out[6]= {{{1, 3, -2, 3}, 5}, {{3, -2, 3}, 4}, {{1, 3, -2, 3, -1}, 4}, {{1, 3}, 4}, {{1, 2, -4, 1, 3, -2, 3}, 4}, {{3}, 3}, {{3, -2, 3, -1}, 3}, {{3}, 3}, {{2, -4, 1, 3, -2, 3}, 3}, {{1, 2, -4, 1, 3, -2, 3, -1}, 3}, {{1, 2, -4, 1, 3}, 3}, {{1, 2}, 3}, {{3, -1}, 2}, {{1, 3, -2}, 2}, {{2, -4, 1, 3, -2, 3, -1}, 2}, {{2, -4, 1, 3}, 2}, {{2}, 2}, {{-2, 3}, 1}, {{3, -2}, 1}, {{1}, 1}, {{-4, 1, 3, -2, 3}, 1}, {{1, 2, -4, 1, 3, -2}, 1}, {{1}, 1}, {{-2, 3, -1}, 0}, {{-4, 1, 3, -2, 3, -1}, 0}, {{-4, 1, 3}, 0}, {{2, -4, 1, 3, -2}, 0}, {{1, 2, -4, 1}, 0}, {{-1}, -1}, {{2, -4, 1}, -1}, {{1, 2, -4}, -1}, {{-2}, -2}, {{-4, 1, 3, -2}, -2}, {{2, -4}, -2}, {{-4, 1}, -3}, {{-4}, -4}} In[7]:= max = subsequencesAndSums[[1]] Out[7]= {{1, 3, -2, 3}, 5} 
Posted 10 years ago
 Ah, yes, that was dense of me. I will give it some more thought....
Posted 10 years ago
 Inspired by Gustavo's use of Partition (it works like a champ) ... here is the over-enumerated, but "functional paradigm", solution.data={1,2,-4,1,3,-2,3,-1}; Max[Total /@ Flatten[Table[ Partition[data, i, j], {i, Length[data]}, {j, Length[data]}], 2]]So, on this (puzzle) example, this solution (gets the right answer, 5) but it generates 121 subsequences in doing so. Using the procedural approach one need examine only a handful of subsequences though with lots of conditional statement executions. (Though I haven't, yet, formulated the worst-case for that approach.)Still asking, is this - functional shortfall - intrinsic?Thank you.
Posted 10 years ago
 This runs in O(n^2) time, not very efficient, as you can do it in O(n) time...
Posted 10 years ago
 First, in response to David's question, the key aspect of the problem definition is the subsequence notion - namely that a subsequence is a consecutive list of 1 or more elements, and not just any subset (as Gustavo observes).Second, in response to Gustavo's interesting suggestion, it's missing some cases - the maximum sum might come from a single (large positive) number, for example. Further, the point of this particular puzzle is to avoid over-enumerating.That said, I'm completely in favor of the over-enumeration one often gets with the use of the functional programming paradigm. I'm just asking if there's a functional approach to this puzzle that doesn't over-enumerate. Or, is this puzzle inherently sequential, and thus centrally "procedural"?
Posted 10 years ago
 Generating all subsequences it can be done like: data={1,2,-4,1,3,-2,3,-1}; Last@SortBy[Flatten[Table[Partition[data,s,1],{s,2,Length[d-1]}],1],Total] David, I infer that the numbers to consider need to be consecutive.
Posted 10 years ago
 What are the rules for this problem? The way I read it, the answer is simply the sum of the positive entries (which would give the answer as 1+2+1+3+3). I am guessing that this is not the interpretation that you are using in getting the answer 1+3-2+3.