Non-continuous subsequences: Difference between revisions
Content added Content deleted
m (Spelling correction in task.) |
mNo edit summary |
||
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-continuous subsequences for a given sequence. Example: For the sequence ''1,2,3,4'', there are five 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-continuous subsequences, namely ''1,3''; ''1,4''; ''2,4''; ''1,3,4'' and ''1,2,4''. |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
Revision as of 17:56, 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-continuous 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]]