Non-continuous subsequences: Difference between revisions
mNo edit summary |
(+D) |
||
Line 9: | Line 9: | ||
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''. |
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|D}}== |
|||
(I may be misunderstood...) The list of non-continuous subsequences is constructed from some what different from task description, but should be equivalent way: |
|||
#from the original sequence, select some continuous subsequences of length >= 3, |
|||
#from each continuous subsequences in (1), remove some in-between elements beside first and last element, |
|||
#each subsequences some elements removed in (2) is a non-continuous subsequences. |
|||
Notes:assumes continuous subsequences of length < 3 does not contain non continuous subsequences, |
|||
<d>module ncsub ; |
|||
import std.stdio ; |
|||
struct Combi { |
|||
private int n_, m_ ; |
|||
alias int delegate(inout int[]) dg_type ; |
|||
int opApply(dg_type dg) { return combinate([], 0, m_, dg) ; } |
|||
int combinate(int[] fixed, int next, int left, dg_type dg) { |
|||
if (left <= 0) dg(fixed) ; |
|||
else |
|||
for(int i = next ; i < n_ - left + 1; i++) |
|||
combinate(fixed ~ [i+1], i + 1, left - 1, dg) ; |
|||
return 0 ; |
|||
} |
|||
} |
|||
T[] takesome(T)(T[] seq, int[] rmIndexs) { |
|||
T[] res = seq.dup ; |
|||
foreach(idx ; rmIndexs.reverse) |
|||
res = res[0..idx] ~ res[idx+1..$] ; |
|||
return res ; |
|||
} |
|||
T[][] ncsub(T)(T[] seq) { |
|||
if(seq.length < 3) return [] ; |
|||
T[][] ncset ; |
|||
for(int head = 0 ; head < seq.length - 2 ; head++) |
|||
for(int tail = head + 2 ; tail < seq.length ; tail++) { |
|||
T[] contseq = seq[head..tail+1] ; |
|||
for(int takeNum = 1 ; takeNum < contseq.length - 1 ; takeNum++) |
|||
foreach(removeIndexs ; Combi(contseq.length - 2, takeNum)) |
|||
ncset ~= takesome(contseq, removeIndexs) ; |
|||
} |
|||
return ncset ; |
|||
} |
|||
void main() { |
|||
writefln(ncsub([1,2,3])) ; |
|||
writefln(ncsub([1,2,3,4])) ; |
|||
writefln(ncsub([1,2,3,4,5])) ; // results match Haskell examples |
|||
writefln(ncsub([1,1,1,1,1])) ; // should this return [] ? that is, no non-cont subseq. |
|||
}</d> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Revision as of 23:57, 27 March 2008
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.
D
(I may be misunderstood...) The list of non-continuous subsequences is constructed from some what different from task description, but should be equivalent way:
- from the original sequence, select some continuous subsequences of length >= 3,
- from each continuous subsequences in (1), remove some in-between elements beside first and last element,
- each subsequences some elements removed in (2) is a non-continuous subsequences.
Notes:assumes continuous subsequences of length < 3 does not contain non continuous subsequences, <d>module ncsub ; import std.stdio ;
struct Combi {
private int n_, m_ ; alias int delegate(inout int[]) dg_type ; int opApply(dg_type dg) { return combinate([], 0, m_, dg) ; } int combinate(int[] fixed, int next, int left, dg_type dg) { if (left <= 0) dg(fixed) ; else for(int i = next ; i < n_ - left + 1; i++) combinate(fixed ~ [i+1], i + 1, left - 1, dg) ; return 0 ; }
}
T[] takesome(T)(T[] seq, int[] rmIndexs) {
T[] res = seq.dup ; foreach(idx ; rmIndexs.reverse) res = res[0..idx] ~ res[idx+1..$] ; return res ;
}
T[][] ncsub(T)(T[] seq) {
if(seq.length < 3) return [] ; T[][] ncset ; for(int head = 0 ; head < seq.length - 2 ; head++) for(int tail = head + 2 ; tail < seq.length ; tail++) { T[] contseq = seq[head..tail+1] ; for(int takeNum = 1 ; takeNum < contseq.length - 1 ; takeNum++) foreach(removeIndexs ; Combi(contseq.length - 2, takeNum)) ncset ~= takesome(contseq, removeIndexs) ; } return ncset ;
}
void main() {
writefln(ncsub([1,2,3])) ; writefln(ncsub([1,2,3,4])) ; writefln(ncsub([1,2,3,4,5])) ; // results match Haskell examples writefln(ncsub([1,1,1,1,1])) ; // should this return [] ? that is, no non-cont subseq.
}</d>
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]]