Which order is "lexicographic order"?

Question

To choose 3 items out of 5 items [1, 2, 3, 4, 5], Donald Knuth's lexicographic algorithm (The Art of Computer Programming, Vol 4A, 2011, p. 358, Algorithm L (lexicographic combinations)) gives:

[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 5], [1, 3, 5], [2, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5]]

or, if strictly following the algorithm, each combination is reversed, making it:

[[3, 2, 1], [4, 2, 1], [4, 3, 1], [4, 3, 2], [5, 2, 1], [5, 3, 1], [5, 3, 2], [5, 4, 1], [5, 4, 2], [5, 4, 3]]

while Combinatorial Algorithms by Nijenhuis and Wilf, 2nd Ed, 1978, p. 26 cited "alphabetic order" or "lexicographic order" of:

[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], ...

so they are different. Which is actually lexicographic order, or are all of them lexicographic order, and why?

Answer 1

There is no one universally accepted lexographical ordering. Any author is free to introduce their own ordering, as long as it is consistent within their scope of discussion.

It's just like binary tree traversing algorithms like preoder, inorder or postorder traversal. There is no one correct traversal, its upto the author to decide which one to use, and stick with it throughout their discussion about the topic.

Answer 2

I think this is the rule: if it is said to be lexicographic, then it is, it follows a particular order, as if the items are printed in a dictionary or phone book.

So for example:

apple
aquarium
banana

the above is the ordering that would be in a dictionary.

It can be:

1.0.0
1.2.18
1.3.0
2.0.1

the above can be considered to be lexicographic, if you consider them to be software version numbers.

And so

[1, 0, 0]
[1, 2, 18]
[1, 3, 0]
[2, 0, 1]

would be lexicographic order too.

Note that

 0.0.1
18.2.1
 0.3.1
 1.0.2

could be considered to be lexicographic also, if somehow, the right hand side is taken to be the most significant. In fact, the numbers above are just the original version numbers but written from right to left.

So can you say

0.1.0
2.1.18
3.1.0
0.2.1

is lexicographic too? I suppose you can, if somehow the most significant starts from the middle and go to the left and then to the right (and then to the left and to the right, if it is the ordering used). But it is just not commonly used.

The simple idea is: usually in the commonly used order: say, from left to right, it can be listed in that order in a dictionary or phone book (or some kind of sorted list).

So if we revisit Knuth's algorithm:

[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 5], [1, 3, 5], [2, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5]]

the above doesn't look like it is "lexicographic", but it is, when you read each item from right to left. If you read each item from right to left, it is the same as the following read from left to right. Looking at the following, it is lexicographic, if you view them as software version numbers, starting with 3.2.1:

[[3, 2, 1], [4, 2, 1], [4, 3, 1], [4, 3, 2], [5, 2, 1], [5, 3, 1], [5, 3, 2], [5, 4, 1], [5, 4, 2], [5, 4, 3]]

(or you can map 3 to "c", 2 to "b", 1 to "a", and the above becomes

[cba, dba, dca, dcb, eba, ... ]

and it is in fact the order how it would appear in a printed dictionary.)

So Wilf's algorithm generates them starting with [1, 2, 3] reading from left to right and work its way up, while Knuth's algorithm starts with [3, 2, 1], also reading from left to right, and work its way up. Both are lexicographic, but in a different sequence.