I think the following algorithm should do what you want (there are obvious optimizations which could be done):
define count(a, b): if a = [] return 1 else if b = [] return 0 else if first(a) = first(b) return count(rest(a), rest(b)) + count(a, rest(b)) else return count(a, rest(b))
Here first(s)
gives the first element of the sequence s
(e.g. first([1,2,2,1,3])
gives 1
), rest(s)
gives the sequence with the first sequence removed (e.g. rest([1,2,2,1,3])
gives [2,2,1,3]
) and []
is the empty sequence. I've used the convention that the empty sequence occurs exactly once in any sequence (this simplified the algorithm).
For example, evaluating count([0,1],[0,1,0,1])
gives in sequence
count([0,1],[0,1,0,1]) → count([1],[1,0,1]) + count([0,1],[1,0,1]) count([1],[1,0,1]) → count([],[0,1]) + count([1], [0,1]) count([],[0,1]) → 1 count([1],[0,1]) → count([1],[1]) count([1],[1]) → count([],[]) + count([1],[]) count([],[]) → 1 count([1],[]) → 0 1 + 0 → 1 1 + 1 → 2 count([0,1],[1,0,1]) → count([0,1],[0,1]) count([0,1],[0,1]) → count([1],[1]) + count([0,1],[1]) count([1],[1]) → count([],[]) + count([1],[]) count([],[]) → 1 count([1],[]) → 0 1 + 0 → 1 count([0,1],[1]) → count([1],[]) count([1],[]) → 0 1 + 0 → 1 2 + 1 → 3
So the algorithm correctly finds 3 different subsequences of [0,1]
in [0,1,0,1]
.