Non-continuous subsequences
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]]