Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A$ and $B$ two finite ordered sets where $A\subseteq B$. How do I count the number of consecutive and non-consecutive ocurrences of $A$ in $B$? For instance, I have nine ocurrences of set $A=\{0,1\}$ in set $B=\{0,0,1,2,3,0,1,2,0,1\}$.

share|improve this question
    
You mean finite sequences, right? As sets $A = \{0,1\}$, $B = \{0,1,2,3\}$ and there is nothing like "number of occurences" ... And: How do you want to count? –  martini Aug 6 '12 at 13:18
    
Are you looking for an algorithm? –  Arthur Fischer Aug 6 '12 at 13:20
    
@martini, I mean finite sequences. For instance, in $B\{0, 1, 2, 0, 1\}$, the ordered subset $A\{0,1\}$ appears twice. I'd like to count this. –  Marcos da Silva Sampaio Aug 6 '12 at 13:21
    
Yes, @ArthurFischer. I'm looking for an algorithm. –  Marcos da Silva Sampaio Aug 6 '12 at 13:21
1  
@Marcos: Then how do you find only $3$ occurrences of 01 in 0012301201? If you're counting non-consecutive subsequences, there would be $9$. –  Henning Makholm Aug 6 '12 at 14:25

2 Answers 2

up vote 0 down vote accepted

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].

share|improve this answer
1  
One of the obvious optimizations one has to apply is to memoize the results of count. Otherwise, the algorithm will produce the result by adding $1$s together, and since the result can be as large as $\binom{|B|}{|A|}$, that can be vey inefficient. –  Henning Makholm Aug 6 '12 at 15:52

What you're looking for is a string searching algorithm. (From an algorithmic point of view there's no relevant difference between sequences of numbers and sequences of characters).

Such algorithms come in a wide variety of choices, providing different tradeoffs between ease of implementation and speed of search.

The simplest is just to look at every position in $B$ sequentially and check whether a copy of $A$ begins there or not. Count the number of successes.


If, on the other hand, you want to count non-contiguous occurrences of $A$ in $B$, I suggest a dynamic-programming approach. For $1\le p\le|A|$ and $1\le q\le |B|$, let $N(p,q)$ be the number of district non-contiguous appearances of the first $p$ elements of $A$ within the first $q$ elements of $B$. Then you can compute $N(p,q)$ recursively $$ N(p,q) = \begin{cases} N(p,q-1)+N(p-1,q-1) & \text{if }A_p=B_q \\ N(p,q-1) & \text{otherwise} \end{cases} $$ plus some easy base cases that I'll let you imagine. If you fill in a table of $N(p,q)$s starting with low $q$s, the entire computation up to $N(|A|,|B|)$ takes time $O(|A|\times|B|)$.

share|improve this answer
    
It does not suffice to count the number of initial positions, as the counting requested is of subsequences, not of subwords. –  Marc van Leeuwen Aug 6 '12 at 14:16
    
@Marc: But the example in the question is clearly counting subwords, not subsequences. –  Henning Makholm Aug 6 '12 at 14:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.