Re: Increasing scattered subsequence

*To*: mathgroup at smc.vnet.net*Subject*: [mg80134] Re: Increasing scattered subsequence*From*: DrMajorBob <drmajorbob at bigfoot.com>*Date*: Mon, 13 Aug 2007 04:37:26 -0400 (EDT)*References*: <fa11b990e477.46baf2d3@bgu.ac.il> <D370EB89-ACFD-4FFF-B4E7-84A25FF267C5@mimuw.edu.pl> <C82B7D4D-6C0B-47E1-8603-DEE030A6E387@mimuw.edu.pl> <f69ab100e04a.46bc3a23@bgu.ac.il> <28688943.1186820838583.JavaMail.root@m35> <op.twwnxqppqu6oor@monster.gateway.2wire.net> <16850717.1186975277176.JavaMail.root@m35>*Reply-to*: drmajorbob at bigfoot.com

> Interesting, but certinly not an answer to the original question True. I responded a bit too quickly, as I often do. Bobby On Sat, 11 Aug 2007 13:02:10 -0500, Andrzej Kozlowski <akoz at mimuw.edu.pl> wrote: > Interesting, but certinly not an answer to the original question (at > least in the sense that I undestood the original question). The question > was to find a subsequence such that each element is larger than all > those that precede it in the original sequence, not in the subsequence. > That's what my code does, anyway. > > Andrzej Kozlowski > > On 11 Aug 2007, at 19:23, DrMajorBob wrote: > >>> On 10 Aug 2007, at 10:12, Ivan Egorov wrote: >>> >> (snip) >>>> Write a function maxima[lis_List] which, given a list of numbers, >>>> produces a list of those numbers greater than all those >>>> that precede them. For example >>>> >>>> maxima[{ 9, 2, 10, 3, 14, 9}] returns { 9, 10, 14}. >> >> Combinatorica includes a function, LongestIncreasingSubsequence, that >> returns the LONGEST increasing scattered subsequence. And here's a >> faster code of my own: >> >> Clear[zeroPad, singleLongest] >> zeroPad[{}] = {0}; >> zeroPad[x_List] := x >> singleLongest[x_List] := >> Module[{t = Append[x, 1 + Max@x], len, pred, path, max}, >> path[i_Integer, o___Integer] /; pred[i] != {} := >> path[Last@pred@i, i, o]; >> len[i_] := len[i] = Module[ >> {mx, prior, pick, nxt = t[[i]]}, >> pick = Pick[Range[i - 1], Take[t, i - 1] - nxt, _?Negative]; >> prior = len /@ pick; >> mx = Max@zeroPad@prior; >> pred[nxt] = t[[Pick[pick, prior, mx]]]; >> 1 + mx]; >> len /@ Range@Length@t; >> Most[(path@Last@t) /. path -> List] >> ] >> >> Needs["Combinatorica`"] >> n = 35; >> s = Ordering@RandomReal[{0, 1}, n^2 + 1]; >> Timing[mine = singleLongest@s] >> Timing[theirs = LongestIncreasingSubsequence@s] >> theirs == mine >> >> {1.39, {51, 64, 89, 131, 143, 148, 189, 193, 195, 197, 241, 255, 318, >> 332, 372, 393, 408, 444, 448, 468, 478, 491, 493, 497, 535, 536, >> 563, 581, 599, 613, 618, 620, 639, 648, 688, 725, 747, 753, 762, >> 766, 767, 802, 842, 850, 876, 950, 960, 961, 998, 1045, 1052, 1076, >> 1084, 1087, 1095, 1101, 1104, 1149, 1168, 1194}} >> >> {12.375, {51, 64, 89, 131, 143, 148, 189, 193, 195, 197, 241, 255, >> 318, 332, 372, 393, 408, 444, 448, 468, 478, 491, 493, 497, 535, >> 536, 563, 581, 599, 613, 618, 620, 639, 648, 688, 725, 747, 753, >> 762, 766, 767, 802, 842, 850, 876, 950, 960, 961, 998, 1045, 1052, >> 1076, 1084, 1087, 1095, 1101, 1104, 1149, 1168, 1194}} >> >> True >> >> I call it "singleLongest" because the following code returns ALL the >> optimal subsequences. >> >> Clear[zeroPad, longest] >> zeroPad[{}] = {0}; >> zeroPad[x_List] := x >> longest[x_List] := >> Module[{t = Append[x, 1 + Max@x], len, pred, path, max}, >> path[i_Integer, o___Integer] /; pred[i] != {} := >> Flatten[path[#, i, o] & /@ pred[i]]; >> len[i_] := len[i] = Module[ >> {mx, prior, pick, nxt = t[[i]]}, >> pick = Pick[Range[i - 1], Take[t, i - 1] - nxt, _?Negative]; >> prior = len /@ pick; >> mx = Max@zeroPad@prior; >> pred[nxt] = t[[Pick[pick, prior, mx]]]; >> 1 + mx]; >> len /@ Range@Length@t; >> (path@Last@t) /. path[any__] :> Most@List[any] >> ] >> >> n = 25; >> s = Ordering@RandomReal[{0, 1}, n^2 + 1]; >> Timing[mine = longest@s;] >> Timing[theirs = LongestIncreasingSubsequence@s] >> MemberQ[mine, theirs] >> Length@theirs >> Length /@ mine // Union >> Length@mine >> >> {0.812, Null} >> >> {3.625, {23, 27, 29, 39, 46, 54, 74, 82, 99, 137, 149, 173, 202, 205, >> 234, 258, 282, 284, 290, 291, 295, 322, 337, 344, 345, 347, 350, >> 351, 411, 421, 435, 445, 453, 461, 480, 520, 540, 568, 569, 592, >> 597, 598, 612, 615}} >> >> True >> >> 44 >> >> {44} >> >> 4536 >> >> "longest" is fast when a reasonable number of optima exist (4536 in >> that problem), but it can be slow in extreme cases: >> >> n = 25; >> s = Ordering@RandomReal[{0, 1}, n^2 + 1]; >> Timing[mine = longest@s;] >> Timing[theirs = LongestIncreasingSubsequence@s] >> MemberQ[mine, theirs] >> Length@theirs >> Length /@ mine // Union >> Length@mine >> >> {59.156, Null} >> >> {3.61, {5, 36, 53, 61, 78, 117, 140, 157, 161, 197, 200, 209, 215, >> 229, 232, 234, 235, 246, 254, 271, 293, 328, 370, 372, 377, 378, >> 380, 385, 391, 398, 406, 416, 435, 451, 460, 474, 512, 514, 528, >> 558, 559, 572, 573, 578, 596, 619}} >> >> True >> >> 46 >> >> {46} >> >> 359250 >> >> In case one NEEDS all 359250 solutions, it's only 16 times slower than >> the built-in that returns just ONE. >> >> Bobby >> >> On Sat, 11 Aug 2007 01:22:04 -0500, Andrzej Kozlowski >> <akoz at mimuw.edu.pl> wrote: >> >>> First, please send such question to the MathGroup, >>> >>> mathgroup at smc.vnet.net >>> >>> not me personally. (I really have desire, tiem or ability to replace >>> the enitre MathGroup.) >>> So I have decided to post this question to the MathGroup in case >>> someone else finds it interesting. >>> >>> Also, there is something about this question and the earlier you sent >>> me that make sme suspicious. What do you say "you need to use >>> recursion and pattern matching, Select and Join"? This sounds to me >>> like some sort of test problem so I have decided to answer it but >>> without using any of these functions (although it may not be the >>> simplest way to do this). So here is my answer: >>> >>> ls = {9, 2, 10, 3, 14, 9}; >>> >>> Reverse[Last[Last[Reap[NestWhile[With[{a = First[Ordering[#, -1]]}, >>> Sow[#[[a]]]; Take[#, a - 1]] &,ls,Length[#] > 0 &]]]]] >>> >>> {9, 10, 14} >>> >>> >>> On 10 Aug 2007, at 10:12, Ivan Egorov wrote: >>> >>>> I have one more question. >>>> >>>> >>>> >>>> Write a function maxima[lis_List] which, given a list of numbers, >>>> produces a list of those >>>> >>>> numbers greater than all those that precede them. For example >>>> >>>> maxima[{ 9, 2, 10, 3, 14, 9}] returns { 9, 10, 14}. You need to use >>>> recursion, pattern matching, >>>> >>>> Select and Join. >>>> >>>> >>>> >>> >>> >>> >> >> >> >> --DrMajorBob at bigfoot.com > > -- DrMajorBob at bigfoot.com