Non-continuous subsequences: Difference between revisions
Content added Content deleted
(Defined task; added Haskell example) |
m (Spelling correction in task.) |
||
Line 7: | Line 7: | ||
A ''continuous'' subsequence is missing elements only before its begin and after its end. |
A ''continuous'' subsequence is missing elements only before its begin and after its end. |
||
The task is to find all non- |
The task is to find all non-continuous subsequences for a given sequence. Example: For the sequence ''1,2,3,4'', there are five non-continous subsequences, namely ''1,3''; ''1,4''; ''2,4''; ''1,3,4'' and ''1,2,4''. |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
Revision as of 17:55, 27 March 2008
Non-continuous subsequences
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
Consider some sequence of elements.
A subsequence contains some, but not all elements of this sequence, in the same order.
A continuous subsequence is missing elements only before its begin and after its end.
The task is to find all non-continuous subsequences for a given sequence. Example: For the sequence 1,2,3,4, there are five non-continous subsequences, namely 1,3; 1,4; 2,4; 1,3,4 and 1,2,4.
Haskell
action p x = if p x then succ x else x fenceM p q s [] = guard (q s) >> return [] fenceM p q s (x:xs) = do (f,g) <- p ys <- fenceM p q (g s) xs return $ f x ys ncsubseq = fenceM [((:), action even), (flip const, action odd)] (>= 3) 0
Output:
*Main> ncsubseq [1..3] [[1,3]] *Main> ncsubseq [1..4] [[1,2,4],[1,3,4],[1,3],[1,4],[2,4]] *Main> ncsubseq [1..5] [[1,2,3,5],[1,2,4,5],[1,2,4],[1,2,5],[1,3,4,5],[1,3,4],[1,3,5],[1,3],[1,4,5],[1,4],[1,5],[2,3,5],[2,4,5],[2,4],[2,5],[3,5]]