Lexicographic order


Martin McBride, 2021-11-02
Tags lexicographic
Categories statistics probability

Lexicographic ordering is similar to dictionary ordering, but it extends the idea to other items, not just letters of the alphabet. It allows us to arrange sequences of items, drawn from a particular set, in a well-defined order.

For example, a word is a sequence of items from the set of letters (a to z). Alphabetic ordering considers each word, letter by letter. So if we compare the words "cat" and "cart":

  • Both words have a first letter "c", so we move on to the next letter.
  • Both words have a second letter "a", so we move on to the next letter.
  • The third letter of "cat" is "t", but the third letter of "cart" is "r", which comes earlier in the alphabet.

Therefore, of course, "cart" comes before "cat" in alphabetical (therefore lexicographical) order.

Lexicographical ordering of numbers

A number is a sequence of items from the set of digits (0 to 9). Consider the two numbers 206 and 2035.

If we arrange those values in increasing numerical order, then clearly 206 comes before 2035.

In lexicographical ordering, we consider each digit in turn:

  • Both numbers have the first digit 2, so we move on to the next digit.
  • Both numbers have a second digit 0, so we move on to the next digit.
  • The third digit of 206 is 6, but the third digit of 2035 is 3, which is smaller.

Therefore 2035 comes before 206 in lexicographical order, even though it is numerically larger.

Lexicographical ordering of other types of data

Suppose we had a collection of counters with colours red, orange, yellow, green, blue, indigo and violet - the rainbow colours:

We can apply lexicographical ordering, provided we define the order of the items in the set. Unlike letters and digits, colours don't have a natural order. But we can specify that we are going to use the rainbow order defined above.

As an example, consider the three colour sequence OGB, and the four colours sequence OGYR.

The first 2 colours are the same in both sequences, but when we compare the third colour, yellow is before blue, therefore OGYR comes before OGB.

If you found this article useful, you might be interested in the book Computer Graphics in Python or other books by the same author.

Prev

Popular tags

2d arrays abstract data type alignment and angle animation arange arc array arrays behavioural pattern bezier curve built-in function callable object chain circle classes clipping close closure cmyk colour combinations comparison operator comprehension context context manager conversion count creational pattern data science data types design pattern device space dictionary drawing duck typing efficiency ellipse else encryption enumerate fill filter font font style for loop function function composition function plot functools game development generativepy tutorial generator geometry gif global variable gradient greyscale higher order function hsl html image image processing imagesurface immutable object in operator index inner function input installing iter iterable iterator itertools join l system lambda function len line linear gradient linspace list list comprehension logical operator lru_cache magic method mandelbrot mandelbrot set map matplotlib monad mutability named parameter numeric python numpy object open operator optimisation optional parameter or pandas partial application path pattern permutations polygon positional parameter print pure function python standard library radial gradient range recipes rectangle recursion reduce repeat rgb rotation roundrect scaling scipy sector segment sequence setup shape singleton slice slicing sound spirograph sprite square str stream string stroke structural pattern subpath symmetric encryption template text text metrics tinkerbell fractal transform translation transparency triangle truthy value tuple turtle unpacking user space vectorisation webserver website while loop zip