Lexicographic order
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.
See also
Join the GraphicMaths Newletter
Sign up using this form to receive an email when new content is added:
Popular tags
adder adjacency matrix alu and gate angle area argand diagram binary maths cartesian equation chain rule chord circle cofactor combinations complex modulus complex polygon complex power complex root cosh cosine cosine rule cpu cube decagon demorgans law derivative determinant diagonal directrix dodecagon eigenvalue eigenvector ellipse equilateral triangle euler eulers formula exponent exponential exterior angle first principles flip-flop focus gabriels horn gradient graph hendecagon heptagon hexagon horizontal hyperbola hyperbolic function hyperbolic functions infinity integration by parts integration by substitution interior angle inverse hyperbolic function inverse matrix irrational irregular polygon isosceles trapezium isosceles triangle kite koch curve l system line integral locus maclaurin series major axis matrix matrix algebra mean minor axis nand gate newton raphson method nonagon nor gate normal normal distribution not gate octagon or gate parabola parallelogram parametric equation pentagon perimeter permutations polar coordinates polynomial power probability probability distribution product rule proof pythagoras proof quadrilateral radians radius rectangle regular polygon rhombus root sech set set-reset flip-flop sine sine rule sinh sloping lines solving equations solving triangles square standard curves standard deviation star polygon statistics straight line graphs surface of revolution symmetry tangent tanh transformation transformations trapezium triangle turtle graphics variance vertical volume volume of revolution xnor gate xor gate