Check ordered subset in list

Question

I need to find a function that checks if a list is contained in a larger list RESPECTING the order of the smaller one. For example check[{a,b,c},{a,d,b,c}] would return True, but check[{a,b,c},{a,c,b,d}] would return False. From what I see, the function SubsetQ doesn't seems to care about the order of the smaller list, but is there any function that does? Thanks in advance.

Answer 1

Assuming that the elements of list1 are contained in list2, you may try:

-Select the elements of list 1 in list 2

-Check if the result is the same (elements AND order) as list 1:

We can define a function that will do this check:

check[l1_, l2_] := l1 === Select[l2, MemberQ[l1, #] &]

Now to test:

check[{a, b, c}, {a, c, b, d}]
(* False *)
check[{a, b, c}, {a, d, b, c}]
(* True *)

Answer 2

largerList = {a, d, b, c, d, a, b, d, c};
smallerList = {a, d, c};

Clear[patt, k]
patt[k_List] := 
 Flatten[Riffle[k, {Shortest[Except[#]] ...} & /@ Rest@k]]

---

For the first example the pattern can be found twice.

SequenceCases[largerList, patt[smallerList]]

{{a, d, b, c}, {a, b, d, c}}

Also:

SequencePosition[largerList, patt[smallerList]]

{{1, 4}, {6, 9}}

---

smallerList = {a, d, f};
SequenceCases[largerList, patt[smallerList]]

{}

If you get an empty list, you can easily return False else True when you write your function using these techniques.

Answer 3

checks if a list is contained in a larger list RESPECTING the order of the smaller one

You could find the Position of each element of {a,b,c} in the other list. This will give you a list of numbers.

Now check if this list is always increasing.

To check if the list of numbers is always increasing, you can use Differences function on it, and look to see if it has no negative value or not. If not, then the order is respected i.e. True , else not i.e. False

Here is an example

L1 = {a, b, c};
L2 = {a, d, b, c};
p1 = Flatten[Position[L2, #] & /@ L1]

Differences[p1]

Since there are no negative values, then the sequence is increasing. Hence True

L3 = {a, c, b, d};
p2 = Flatten[Position[L3, #] & /@ L1]

Differences[p2]

Since there is negative value, then the sequence is not always increasing. Hence False

These can be easily made into a function if this meets what you want.

---

Here is the above in a function

check[lis1_List, lis2_List] := Module[{p},
  p = Flatten[Position[lis2, #] & /@ lis1];
  If[Select[Differences[p], # < 0 &] =!= {}, False, True]
  ]

And now

check[{a, b, c}, {a, d, b, c}]

check[{a, b, c}, {a, c, b, d}]

Ofcourse in Mathematica there is always at least 10 different ways to do the same thing :)

Answer 4

Using ContainsOrderedItemsQ by Jon McLoone and Daniel Robinson

ContainsOrderedItemsQ = ResourceFunction["ContainsOrderedItemsQ"];

check[a_, b_] :=
 With[{x = ReverseSortBy[Length] @ {a, b}}, ContainsOrderedItemsQ @@ x]

check[{a, b, c}, {a, d, b, c}]

True

check[{a, c, b, d}, {a, b, c}]

False

Because of ReverseSortBy (new in 12.0) we can pass the two lists in any order