Lexicographic ordering.


R. Clayton (rclayton@clayton.cs.monmouth.edu)
(no date)


Chapter 19 in the the book says that s1 > s2 is true if string s1 is
lexiographically greater than string s2. What does this mean?

  Another name for lexicographic order is dictionary order; the order in which
  you alphabetize words.

  Let A be an array of m elements of type T and and B be an array of n elements
  of type T (m need not equal n), and let the relations < and == be defined on
  values of type T.

  The lexicographic ordering <= is defined over arrays as follows: A <= B
  exactly when one of the following is true

    1 there exists some i, 0 <= i < min(m, n), such that A[j] == B[j] for all 0
      <= j < i and A[i] < B[i]

  or

    2 m <= n and A[i] == B[i] for al 0 <= i < m

  For example, suppose A = "sweater" (m = 7) and B = "sweet" (n = 5). Case 1
  holds because A[3] = 'a' < B[3] = 'e' and for all j, 0 < j < 3, A[j] == B[j].
  From this, "sweater" <= "sweet", which the dictionary will verify.

  Now suppose A = "cow" (m = 3) and B = "coworker" (n = 8). Case 2 holds
  because m <= n and for all j, 0 < j < m, A[j] == B[j]. From this, "cow" <=
  "coworker".

  The order over the element type T is sometimes known as the collating
  sequence.



This archive was generated by hypermail 2.0b3 on Mon Aug 13 2001 - 15:00:04 EDT