Help with Bird problem 4.5.6: sequence of successive maxima
This Bird problem vexes me, in the first instance because it doesn't seem to specify a unique solution: Given a list xs = [x_1, x_2, . . . , x_n], the sequence of successive maxima "ssm xs" is the longest subsequence [x_j1, x_j2, x_j3..x_jk] such that j_1 = 1 and j_m < j_n => x_jm < x_jn. For example, xs = [3, 1, 3, 4, 9, 2, 10, 7] => ssm xs = [3, 4, 9, 10]. Define "ssm" in terms of "foldl".
From this specification, I infer:
ssm [] = [] ssm [1] = [1] ssm [1, 2, 3] = [1, 2, 3] ssm [1, 0, 3, 2] = [1, 3] However, what is ssm [1,0,100,2,3,4,5]? Is it [1, 100] or [1, 2, 3, 4, 5]? I think the latter, but am not certain. Whichever it is, what's the solution? Thanks. _________________________________________________________________ Windows Live™ Groups: Create an online spot for your favorite groups to meet. http://windowslive.com/online/groups?ocid=TXT_TAGLM_WL_groups_032009
Am Sonntag, 15. März 2009 21:09 schrieb R J:
This Bird problem vexes me, in the first instance because it doesn't seem to specify a unique solution:
Given a list xs = [x_1, x_2, . . . , x_n], the sequence of successive maxima "ssm xs" is the longest subsequence [x_j1, x_j2, x_j3..x_jk] such that j_1 = 1 and j_m < j_n => x_jm < x_jn. For example, xs = [3, 1, 3, 4, 9, 2, 10, 7] => ssm xs = [3, 4, 9, 10]. Define "ssm" in terms of "foldl".
From this specification, I infer:
ssm [] = [] ssm [1] = [1] ssm [1, 2, 3] = [1, 2, 3] ssm [1, 0, 3, 2] = [1, 3]
However, what is ssm [1,0,100,2,3,4,5]? Is it [1, 100] or [1, 2, 3, 4, 5]? I think the latter, but am not certain.
Since [1,2,3,4,5] is longer than [1,100], it's the former. But if we consider the example [1,0,3,2], the two lists [1,3] and [1,2] are equally long, both are valid answers given the above spec. So if you want one list as the answer, you have to add a criterium to choose.
Whichever it is, what's the solution?
Is the above all that Bird gives as specification or was there more?
Thanks.
Am Sonntag, 15. März 2009 21:09 schrieb R J:
This Bird problem vexes me, in the first instance because it doesn't seem to specify a unique solution:
Given a list xs = [x_1, x_2, . . . , x_n], the sequence of successive maxima "ssm xs" is the longest subsequence [x_j1, x_j2, x_j3..x_jk] such that j_1 = 1 and j_m < j_n => x_jm < x_jn. For example, xs = [3, 1, 3, 4, 9, 2, 10, 7] => ssm xs = [3, 4, 9, 10]. Define "ssm" in terms of "foldl".
From this specification, I infer:
ssm [] = [] ssm [1] = [1] ssm [1, 2, 3] = [1, 2, 3] ssm [1, 0, 3, 2] = [1, 3]
However, what is ssm [1,0,100,2,3,4,5]? Is it [1, 100] or [1, 2, 3, 4, 5]? I think the latter, but am not certain. Whichever it is, what's the solution?
Thanks.
Not particularly efficient, but module SSM where import Data.List (maximumBy) import Data.Ord ssm :: Ord a => [a] -> [a] ssm = reverse . maximumBy (comparing length) . foldl comb [[]] where comb [[]] a = [[a]] comb lists a = do xs@(h:_) <- lists if h < a then [xs,a:xs] else [xs] I think it is impossible to implement ssm as foldl f z without any post-processing and since foldl can't foresee what comes in the remainder of the list, you must keep several candidates around. You can probably make it more efficient by removing all lists lst@(h:_) where there's a longer list with head <= h or an equally long list with head < h in the store (but doing that efficiently is not trivial).
This Bird problem vexes me, in the first instance because it doesn't seem to specify a unique solution:
Given a list xs = [x_1, x_2, . . . , x_n], the sequence of successive maxima "ssm xs" is the longest subsequence [x_j1, x_j2, x_j3..x_jk] such that j_1 = 1 and j_m < j_n => x_jm < x_jn. For example, xs = [3, 1, 3, 4, 9, 2, 10, 7] => ssm xs = [3, 4, 9, 10]. Define "ssm" in terms of "foldl". Hi,
R J schrieb: this problem is a variant of http://en.wikipedia.org/wiki/Longest_increasing_subsequence discussed about a year ago: http://www.mail-archive.com/haskell-cafe@haskell.org/msg39784.html http://www.mail-archive.com/haskell-cafe@haskell.org/msg39844.html In the latter mail, Chris Kuklewicz presents an (efficient) implementation. To solve the problem you stated, simply reuse `lnds`:
-- ssm [3, 1, 3, 4, 9, 2, 9, 10, 7] = [3,4,9,10] ssm (x:xs) = x : lnds (filter (> x) xs)
benedikt
From this specification, I infer:
ssm [] = [] ssm [1] = [1] ssm [1, 2, 3] = [1, 2, 3] ssm [1, 0, 3, 2] = [1, 3]
However, what is ssm [1,0,100,2,3,4,5]? Is it [1, 100] or [1, 2, 3, 4, 5]? I think the latter, but am not certain. Whichever it is, what's the solution?
Thanks.
------------------------------------------------------------------------ Windows Live™ Groups: Create an online spot for your favorite groups to meet. Check it out. http://windowslive.com/online/groups?ocid=TXT_TAGLM_WL_groups_032009
------------------------------------------------------------------------
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (3)
-
Benedikt Huber -
Daniel Fischer -
R J