# Counting subsequences matching a pattern

Given a sequence $(a_1, a_2, \ldots, a_n)$ and a number $m$, I'd like to count the number of subsequences $(a_{i_1},a_{i_2},a_{i_3})$ such that $a_{i_2} < m \leq a_{i_1}, a_{i_3}$.

For example, if the sequence is $(4,2,1,3)$ and $m = 3$, then there are two such subsequences, namely $(4,2,3)$ and $(4,1,3)$.

I solved the problem in two steps: transforming the list into a $0-1$ list using

binary[list_List, m_Integer] :=
Table[If[list[[i]] < m, 0, 1], {i, 1, Length[list]}]


allows us to count the $(1,0,1)$ subsequences several different ways, including

SequenceCount[binary[list, m], {1, ___, 0, ___, 1}, Overlaps -> All]


This seems to work fine, but now I'm trying to eliminate the first transformation and use SequenceCount with a pattern on the original list directly; however the following does not work as it returns 1 instead of 2:

list = {4, 2, 1, 3}; m = 3;
SequenceCount[list, {x_, ___, y_, ___, z_} /; x >= m && y < m && z >= m, Overlaps -> All]


What is the problem with the second approach? I suspect that the conditional pattern is wrong, but I cannot figure out why. Neither SequenceCases nor SequencePosition help.

Bonus question: is there a 'better', more efficient way to do this?

• Welcome! To make the most of Mma.SE start by taking the tour now. It will help us to help you if you write an excellent question. Edit if improvable, show due diligence, give brief context, include minimal working example of code and data in formatted form. As you receive give back, vote and answer questions, keep the site useful, be kind, correct mistakes and share what you have learned. – rhermans Sep 25 '17 at 19:42

I think there is some sort of pattern bug here. It appears that, as expected, SequenceCases deletes duplicates before it returns its result.

With

list = {4, 2, 1, 3};


{x_, ___, y_, ___, z_} /; (x >= m && y < m && z >= m)


in the sequence function will return the entire list in both cases as both start with 4 and end with 3. When duplicates are deleted only once result is returned.

SequenceCases[list,
{x_, ___, y_, ___, z_} /; (x >= m && y < m && z >= m),
Overlaps -> All]

{{4, 2, 1, 3}}


You need to specify which items your want to return so that unique subsets are return for each case.

SequenceCases[list,
{x_, ___, y_, ___, z_} /; (x >= m && y < m && z >= m) :> {x, y, z},
Overlaps -> All]

{{4, 2, 3}, {4, 1, 3}}


However, this presents a dilemma for SequenceCount as without the RuleDelayed it finds only one sequence, as explained above.

SequenceCount[list,
{x_, ___, y_, ___, z_} /; (x >= m && y < m && z >= m),
Overlaps -> All]

1


But it completely fails when the sublist to return is specified.

SequenceCount[list,
{x_, ___, y_, ___, z_} /; (x >= m && y < m && z >= m) :> {x, y, z},
Overlaps -> All]

0


I am of the opinion that this is a bug in SequenceCount. Comments?

• Thanks for the answer! I agree with your conclusion, there seems to be a bug in the conditional pattern matching here. One question: why do you expect SequenceCount to delete duplicates? Without conditions it does return duplicate results: list = {1, 0, 0, 1}; SequenceCases[list, {1, ___, 0, ___, 1}, Overlaps -> All] – ubalage Sep 26 '17 at 7:37