ArrayTools
IsSubsequence
determine if one 1-D container is a subsequence of another 1-D container
Calling Sequence
Parameters
Options
Description
Examples
Compatibility
IsSubsequence( A, B, options )
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
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.
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 are scanned for matches from left-to-right. Similarly, when direction=reverse, elements of B are scanned from right-to-left.
When output includes indices, the indices of matches encountered in B are 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 corresponds 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.
withArrayTools:
Example 1
A1≔Array1,3,5
A1≔135
A2≔Array2,4,6
A2≔246
B≔Array1,2,3,4,5
B≔12345
IsSubsequenceA1,B
true
IsSubsequenceA2,B
false
Example 2
IsSubsequencea,b,a,b,c
IsSubsequenceb,a,a,b,c
Example 3
Scanning can be performed from the left and from the right, and the indices returned can depend on the choice:
A≔Vectorcolumn2,4
A≔24
B≔Vectorrowseq1..10,seq1..10
B≔1234567891012345678910
IsSubsequenceA,B,direction=forward
IsSubsequenceA,B,direction=forward,output=indices
2,4
IsSubsequenceA,B,direction=reverse
IsSubsequenceA,B,direction=reverse,output=indices
12,14
Example 4
Indices can be returned even when the first container is not a subsequence of the second:
B≔Array27,3,18,21,15,12,30,9,24,6
B≔27318211512309246
A1≔Array3,15,9
A1≔3159
IsSubsequenceA1,B,output=check,indices
true,2,5,8
A2≔Array18,30,21
A2≔183021
IsSubsequenceA2,B,direction=forward,output=check,indices
false,3,7
IsSubsequenceA2,B,direction=reverse,output=check,indices
false,4
Example 5
Custom comparisons can be passed:
A≔1.1,2.8,5.3
B≔1,2,3,4,5
IsSubsequenceA,B
f := proc( u, v ) evalb( abs( u - v ) < 0.3 ); end proc;
f ≔ procu,vevalbabsu − v<0.3end proc
g := proc( u, v ) evalb( abs( u - v ) <= 0.3 ); end proc;
g ≔ procu,vevalbabsu − v<=0.3end proc
h := proc( u, v, w ) evalb( abs( u - v ) <= w ); end proc;
h ≔ procu,v,wevalbabsu − v<=wend proc
IsSubsequenceA,B,match=f
IsSubsequenceA,B,match=g
IsSubsequenceA,B,match=h,0.29
IsSubsequenceA,B,match=h,0.30
Example 6
Comparisons for strings can be made with wildcards:
A1≔a*,c*,e*
A2≔a*,C*,e*
B≔aaa,bbb,ccc,ddd,eee
IsSubsequenceA1,B,match=wildcard
IsSubsequenceA2,B,match=wildcard
Example 7
Comparisons for strings can be made with regular expressions:
A≔a[0-1],a[2-3],a[4-5],a[6-7],a[8-9]
B≔seqcata,i,i=0..9
B≔a0,a1,a2,a3,a4,a5,a6,a7,a8,a9
IsSubsequenceA,B,match=regexp,direction=forward,output=check,indices
true,1,3,5,7,9
IsSubsequenceA,B,match=regexp,direction=reverse,output=check,indices
true,2,4,6,8,10
Example 8
Consider the following containers:
B≔Arrayexp1,π,γ
B≔ⅇπγ
A≔evalf5B2,3
A≔3.14160.57722
Due to the truncation, A is not a subsequence of B when match=exact:
However, if we use match=float with an appropriate choice for digits, we can confirm that A is a subsequence of B:
IsSubsequenceA,B,match=float
IsSubsequenceA,B,match=float,digits=5,ulp=1
The ArrayTools:-IsSubsequence command was introduced in Maple 2023.
For more information on Maple 2023 changes, see Updates in Maple 2023.
See Also
ArrayTools:-Lookup
Download Help Document
