 StringTools - Maple Programming Help

Home : Support : Online Help : Programming : Names and Strings : StringTools Package : Comparisons : StringTools/Order

StringTools

 LexOrder
 perform lexicographical order comparison of strings
 ShortLexOrder
 perform short lexicographical order comparison of strings
 RevLexOrder
 perform reverse lexicographical order comparison of strings
 ShortRevLexOrder
 perform short reverse lexicographical order comparison of strings
 LeftRecursivePathOrder
 perform left recursive path order comparison of strings
 RightRecursivePathOrder
 perform right recursive path order comparison of strings

 Calling Sequence LexOrder( s1, s2 ) ShortLexOrder( s1, s2 ) RevLexOrder( s1, s2 ) ShortRevLexOrder( s1, s2 ) LeftRecursivePathOrder( s1, s2 ) RightRecursivePathOrder( s1, s2 )

Parameters

 s1, s2 - Maple strings

Description

 • These six procedures implement various order relations on strings, extended from the numeric order on character code points.
 • Each procedure takes two strings s1 and s2 as arguments, and returns one of the values $-1,0,1$, according to the following table.

 String Order Return Value s1 precedes s2 -1 s1 is identical to s2 0 s1 follows s2 1

 • The LexOrder(s1, s2) command implements simple lexicographic (dictionary) ordering of strings.
 • The RevLexOrder(s1, s2) command implements the reverse lexicographic order, which is equivalent to the lexicographic order on the reversed strings.
 • The ShortLexOrder(s1, s2) and ShortRevLexOrder(s1, s2) commands are similar, but apply the respective ordering relation only to strings of equal length. Strings are first compared according to their lengths, with shorter strings preceeding longer strings. The short variants are important because they are translation-invariant: $\mathrm{ShortLexOrder}\left(u,v\right)$ = $\mathrm{ShortLexOrder}\left(\mathrm{cat}\left(u,w\right),\mathrm{cat}\left(v,w\right)\right)$, $\mathrm{ShortLexOrder}\left(u,v\right)$ = $\mathrm{ShortLexOrder}\left(\mathrm{cat}\left(w,u\right),\mathrm{cat}\left(w,v\right)\right)$, $\mathrm{ShortRevLexOrder}\left(u,v\right)$ = $\mathrm{ShortRevLexOrder}\left(\mathrm{cat}\left(u,w\right),\mathrm{cat}\left(v,w\right)\right)$ and $\mathrm{ShortRevLexOrder}\left(u,v\right)$ = $\mathrm{ShortRevLexOrder}\left(\mathrm{cat}\left(w,u\right),\mathrm{cat}\left(w,v\right)\right)$,
 • The left and right recursive path orders are also translation invariant, and are computed by the LeftRecursivePathOrder(s1, s2) and RightRecursivePathOrder(s1, s2) commands, respectively.
 • The left and right recursive path orders, manifest in the LeftRecursivePathOrder(s1, s2) and RightRecursivePathOrder(s1, s2) commands, are defined for two strings $s$ and $t$, as follows. Characters (strings with length equal to 1) compare according to the numeric order of the corresponding code points.
 • String $s$ precedes string $t$ in the left recursive path order if one among the following holds: (1) ${s}_{-1}={t}_{-1}$ and ${s}_{1..-2}$ precedes ${t}_{1..-2}$; (2) ${t}_{-1}<{s}_{-1}$ and ${s}_{1..-2}$ precedes $t$; or (3) ${s}_{-1}<{t}_{-1}$ and $s$ precedes ${t}_{1..-2}$.
 String $s$ precedes string $t$ in the right recursive path order if one among the following holds: (1) ${s}_{1}={t}_{1}$ and ${s}_{2..-1}$ precedes ${t}_{2..-1}$; (2) ${t}_{1}<{s}_{1}$ and ${s}_{2..-1}$ precedes $t$; or (3) ${s}_{1}<{t}_{1}$ and $s$ precedes ${t}_{2..-1}$.
 • All of the StringTools package commands treat strings as (null-terminated) sequences of $8$-bit (ASCII) characters.  Thus, there is no support for multibyte character encodings, such as unicode encodings.

Examples

 > $\mathrm{with}\left(\mathrm{StringTools}\right):$
 > $\mathrm{LexOrder}\left("abc","abd"\right)$
 ${-1}$ (1)
 > $\mathrm{LexOrder}\left("abd","abcd"\right)$
 ${1}$ (2)
 > $\mathrm{ShortLexOrder}\left("abd","abcd"\right)$
 ${-1}$ (3)
 > $\mathrm{RevLexOrder}\left("bcd","abd"\right)$
 ${1}$ (4)
 > $\mathrm{RevLexOrder}\left("bcd","bd"\right)$
 ${1}$ (5)
 > $\mathrm{ShortRevLexOrder}\left("aba","abc"\right)$
 ${-1}$ (6)
 > $\mathrm{ShortRevLexOrder}\left("abc","abc"\right)$
 ${0}$ (7)
 > $\mathrm{LeftRecursivePathOrder}\left("abc","abcc"\right)$
 ${-1}$ (8)
 > $\mathrm{RightRecursivePathOrder}\left("abc","acc"\right)$
 ${-1}$ (9)