ArrayTools/IsSubsequence - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Home : Support : Online Help : ArrayTools/IsSubsequence

ArrayTools

 IsSubsequence
 determine if one 1-D container is a subsequence of another 1-D container

 Calling Sequence IsSubsequence( A, B, options )

Parameters

 A, B - 1-D rtables or lists. options - (optional) equation(s) of the form keyword = value, where keyword is one of digits, direction, match, output, relativeerror, or ulp.

Options

 • digits: Positive integer, specifies the working precision used for floating-point calculations and comparisons. The default is Digits.
 • direction: Either forward or reverse, specifies if scanning is to be performed in the forward direction or in reverse. The default is forward.
 • match: Specifies how matches are to be determined. There are a few options:
 – exact: Matches have to be exact to be counted. This is the default.
 – float: Matches are determined using floating-point comparisons.
 – regexp: Matches strings using regular expressions.
 – wildcard: Matches strings using wildcards.
 – An expression of type callable (e.g. procedure). If match=f, then f(a,b), where a is a value in A and b is a value in B, must return either true (for a match) or false.
 – List of the form [callable,...]. If match=[f,rest], where rest is the expression sequence of remaining elements in the list, then f(a,b,rest), where a is a value in A and b is a value in B, must return either true (for a match) or false.
 • relativeerror: Either true or false, specifies if floating-point errors are to be measured in absolute or relative terms. The default is true.
 • ulp: Positive integer, specifies the number of units in the last place to be used for floating-point comparisons. The default is 1.
 • output: The type of output. The supported options are:
 – check: Either true or false, the result of checking if A is a subsequence of B. This is the default.
 – indices: List of integers for the indices of matches found while checking if A is a subsequence of B.
 – list of any of the above options: Returns an expression sequence with the corresponding outputs, in the same order.

Description

 • The IsSubsequence command determines if A is a subsequence of B, where A and B are 1-D rtables or lists. Here, A is a subsequence of B when there is a list K of strictly increasing indices such that B[K]=A.
 • When direction=forward, elements of B will be scanned for matches from left-to-right. Similarly, when direction=reverse, elements of B will be scanned from right-to-left.
 • When output includes indices, the indices of matches encountered in B will be returned, even if it is determined that A is not a subsequence of B.
 • When match=float, all data must be coercible to software or hardware floats, and comparisons are made with the digits, relativeerror, and ulp options providing flexibility and tolerance. When Digits<=evalhf(Digits) and UseHardwareFloats<>false, rtables with hardware floats and external code will be employed. Note that in this case, it is most efficient to pass numeric data in containers that already have the same hardware datatype (either float[8] or complex[8]).
 • Comparisons when match=regexp and match=wildcard are made, respectively, with the StringTools:-RegMatch and StringTools:-WildcardMatch commands.
 When B is a 1-D Array with initial index different than 1 and output includes indices, the indices list will correspond to the indices of B as opposed to an alias of B with initial index 1.
 When A is empty, A is considered to be a subsequence of B.
 • The command works fastest when:
 – match is exact and either the data consists solely of integers or the size of A is much smaller than the size of B; or
 – match is float.

Examples

 > $\mathrm{with}\left(\mathrm{ArrayTools}\right):$

Example 1

 > $\mathrm{A1}≔\mathrm{Array}\left(\left[1,3,5\right]\right)$
 ${\mathrm{A1}}{≔}\left[\begin{array}{ccc}{1}& {3}& {5}\end{array}\right]$ (1)
 > $\mathrm{A2}≔\mathrm{Array}\left(\left[2,4,6\right]\right)$
 ${\mathrm{A2}}{≔}\left[\begin{array}{ccc}{2}& {4}& {6}\end{array}\right]$ (2)
 > $B≔\mathrm{Array}\left(\left[1,2,3,4,5\right]\right)$
 ${B}{≔}\left[\begin{array}{ccccc}{1}& {2}& {3}& {4}& {5}\end{array}\right]$ (3)
 > $\mathrm{IsSubsequence}\left(\mathrm{A1},B\right)$
 ${\mathrm{true}}$ (4)
 > $\mathrm{IsSubsequence}\left(\mathrm{A2},B\right)$
 ${\mathrm{false}}$ (5)

Example 2

 > $\mathrm{IsSubsequence}\left(⟨"a","b"⟩,⟨"a","b","c"⟩\right)$
 ${\mathrm{true}}$ (6)
 > $\mathrm{IsSubsequence}\left(⟨"b","a"⟩,⟨"a","b","c"⟩\right)$
 ${\mathrm{false}}$ (7)

Example 3

 • Scanning can be performed from the left and from the right, and the indices returned can depend on the choice:
 > $A≔{\mathrm{Vector}}_{'\mathrm{column}'}\left(\left[2,4\right]\right)$
 ${A}{≔}\left[\begin{array}{c}{2}\\ {4}\end{array}\right]$ (8)
 > $B≔{\mathrm{Vector}}_{'\mathrm{row}'}\left(\left[\mathrm{seq}\left(1..10\right),\mathrm{seq}\left(1..10\right)\right]\right)$
 ${B}{≔}\left[\begin{array}{cccccccccccccccccccc}{1}& {2}& {3}& {4}& {5}& {6}& {7}& {8}& {9}& {10}& {1}& {2}& {3}& {4}& {5}& {6}& {7}& {8}& {9}& {10}\end{array}\right]$ (9)
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{direction}'='\mathrm{forward}'\right)$
 ${\mathrm{true}}$ (10)
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{direction}'='\mathrm{forward}','\mathrm{output}'='\mathrm{indices}'\right)$
 $\left[{2}{,}{4}\right]$ (11)
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{direction}'='\mathrm{reverse}'\right)$
 ${\mathrm{true}}$ (12)
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{direction}'='\mathrm{reverse}','\mathrm{output}'='\mathrm{indices}'\right)$
 $\left[{12}{,}{14}\right]$ (13)

Example 4

 • Indices can be returned even when the first container is not a subsequence of the second:
 > $B≔\mathrm{Array}\left(\left[27,3,18,21,15,12,30,9,24,6\right]\right)$
 ${B}{≔}\left[\begin{array}{cccccccccc}{27}& {3}& {18}& {21}& {15}& {12}& {30}& {9}& {24}& {6}\end{array}\right]$ (14)
 > $\mathrm{A1}≔\mathrm{Array}\left(\left[3,15,9\right]\right)$
 ${\mathrm{A1}}{≔}\left[\begin{array}{ccc}{3}& {15}& {9}\end{array}\right]$ (15)
 > $\mathrm{IsSubsequence}\left(\mathrm{A1},B,'\mathrm{output}'=\left['\mathrm{check}','\mathrm{indices}'\right]\right)$
 ${\mathrm{true}}{,}\left[{2}{,}{5}{,}{8}\right]$ (16)
 > $\mathrm{A2}≔\mathrm{Array}\left(\left[18,30,21\right]\right)$
 ${\mathrm{A2}}{≔}\left[\begin{array}{ccc}{18}& {30}& {21}\end{array}\right]$ (17)
 > $\mathrm{IsSubsequence}\left(\mathrm{A2},B,'\mathrm{direction}'='\mathrm{forward}','\mathrm{output}'=\left['\mathrm{check}','\mathrm{indices}'\right]\right)$
 ${\mathrm{false}}{,}\left[{3}{,}{7}\right]$ (18)
 > $\mathrm{IsSubsequence}\left(\mathrm{A2},B,'\mathrm{direction}'='\mathrm{reverse}','\mathrm{output}'=\left['\mathrm{check}','\mathrm{indices}'\right]\right)$
 ${\mathrm{false}}{,}\left[{4}\right]$ (19)

Example 5

 • Consider the following containers:
 > $B≔\mathrm{Array}\left(\left[ⅇ,\mathrm{Pi},\mathrm{gamma}\right]\right)$
 ${B}{≔}\left[\begin{array}{ccc}{ⅇ}& {\mathrm{\pi }}& {\mathrm{\gamma }}\end{array}\right]$ (20)
 > $A≔{\mathrm{evalf}}_{5}\left({B}_{\left[2,3\right]}\right)$
 ${A}{≔}\left[\begin{array}{cc}{3.1416}& {0.57722}\end{array}\right]$ (21)
 • Due to the truncation, A is not a subsequence of B when match=exact:
 > $\mathrm{IsSubsequence}\left(A,B\right)$
 ${\mathrm{false}}$ (22)
 • However, if we use match=float with an appropriate choice for digits, we can confirm that A is a subsequence of B:
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{match}'='\mathrm{float}'\right)$
 ${\mathrm{false}}$ (23)
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{match}'='\mathrm{float}','\mathrm{digits}'=5,'\mathrm{ulp}'=1\right)$
 ${\mathrm{true}}$ (24)

Example 6

 • Custom comparisons can be passed:
 > $A≔\left[1.1,2.8,5.3\right]$
 ${A}{≔}\left[{1.1}{,}{2.8}{,}{5.3}\right]$ (25)
 > $B≔\left[1,2,3,4,5\right]$
 ${B}{≔}\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}\right]$ (26)
 > $\mathrm{IsSubsequence}\left(A,B\right)$
 ${\mathrm{false}}$ (27)
 > f := proc( u, v ) evalb( abs( u - v ) < 0.3 ); end proc;
 ${f}{≔}{\mathbf{proc}}\left({u}{,}{v}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{evalb}}{}\left({\mathrm{abs}}{}\left({u}{-}{v}\right){<}{0.3}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (28)
 > g := proc( u, v ) evalb( abs( u - v ) <= 0.3 ); end proc;
 ${g}{≔}{\mathbf{proc}}\left({u}{,}{v}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{evalb}}{}\left({\mathrm{abs}}{}\left({u}{-}{v}\right){<=}{0.3}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (29)
 > h := proc( u, v, w ) evalb( abs( u - v ) <= w ); end proc;
 ${h}{≔}{\mathbf{proc}}\left({u}{,}{v}{,}{w}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{evalb}}{}\left({\mathrm{abs}}{}\left({u}{-}{v}\right){<=}{w}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (30)
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{match}'=f\right)$
 ${\mathrm{false}}$ (31)
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{match}'=g\right)$
 ${\mathrm{true}}$ (32)
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{match}'=\left[h,0.29\right]\right)$
 ${\mathrm{false}}$ (33)
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{match}'=\left[h,0.30\right]\right)$
 ${\mathrm{true}}$ (34)

Example 7

 • Comparisons for strings can be made with wildcards:
 > $\mathrm{A1}≔\left["a*","c*","e*"\right]$
 ${\mathrm{A1}}{≔}\left[{"a*"}{,}{"c*"}{,}{"e*"}\right]$ (35)
 > $\mathrm{A2}≔\left["a*","C*","e*"\right]$
 ${\mathrm{A2}}{≔}\left[{"a*"}{,}{"C*"}{,}{"e*"}\right]$ (36)
 > $B≔\left["aaa","bbb","ccc","ddd","eee"\right]$
 ${B}{≔}\left[{"aaa"}{,}{"bbb"}{,}{"ccc"}{,}{"ddd"}{,}{"eee"}\right]$ (37)
 > $\mathrm{IsSubsequence}\left(\mathrm{A1},B,'\mathrm{match}'='\mathrm{wildcard}'\right)$
 ${\mathrm{true}}$ (38)
 > $\mathrm{IsSubsequence}\left(\mathrm{A2},B,'\mathrm{match}'='\mathrm{wildcard}'\right)$
 ${\mathrm{false}}$ (39)

Example 8

 • Comparisons for strings can be made with regular expressions:
 > $A≔\left["a\left[0-1\right]","a\left[2-3\right]","a\left[4-5\right]","a\left[6-7\right]","a\left[8-9\right]"\right]$
 ${A}{≔}\left[{"a\left[0-1\right]"}{,}{"a\left[2-3\right]"}{,}{"a\left[4-5\right]"}{,}{"a\left[6-7\right]"}{,}{"a\left[8-9\right]"}\right]$ (40)
 > $B≔\left[\mathrm{seq}\left(\mathrm{cat}\left("a",i\right),i=0..9\right)\right]$
 ${B}{≔}\left[{"a0"}{,}{"a1"}{,}{"a2"}{,}{"a3"}{,}{"a4"}{,}{"a5"}{,}{"a6"}{,}{"a7"}{,}{"a8"}{,}{"a9"}\right]$ (41)
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{match}'='\mathrm{regexp}','\mathrm{direction}'='\mathrm{forward}','\mathrm{output}'=\left['\mathrm{check}','\mathrm{indices}'\right]\right)$
 ${\mathrm{true}}{,}\left[{1}{,}{3}{,}{5}{,}{7}{,}{9}\right]$ (42)
 > $\mathrm{IsSubsequence}\left(A,B,'\mathrm{match}'='\mathrm{regexp}','\mathrm{direction}'='\mathrm{reverse}','\mathrm{output}'=\left['\mathrm{check}','\mathrm{indices}'\right]\right)$
 ${\mathrm{true}}{,}\left[{2}{,}{4}{,}{6}{,}{8}{,}{10}\right]$ (43)

Compatibility

 • The ArrayTools:-IsSubsequence command was introduced in Maple 2023.
 • For more information on Maple 2023 changes, see Updates in Maple 2023.