3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Lexicographic order is defined for strings, given an ordering of the alphabet. The difference seems to be how you convert a subset to a string, and how you order the natural numbers. $\endgroup$ – Yuval Filmus Aug 1 at 15:16
  • $\begingroup$ @太極者 Are you referring to this algorithm? $\endgroup$ – Apass.Jack Aug 1 at 19:35
  • $\begingroup$ @Apass.Jack it is Algorithm L, yes... in fact let me added to the original question. Knuth's algorithm is sometimes hard to follow, as it may have "go to" statements or "terminate here"... some of the other algorithms in Knuth's book I had to think: how do I actually write a "go to" in Ruby or Python $\endgroup$ – nopole Aug 19 at 23:20
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I sort of grabbed the lexicographic ordering: if each number is less than 10, meaning it is at most 9, then you really can "join the numbers" or "join the digits". So Donald Knuth's answer is 321, 421, 431, ... so note it is strictly increasing, or "lexicographic". In the case of Wilf, it is going with 123, 124, 125, 134, and note again, the numbers are strictly increasing as well. So yes, both are "lexicographic". And if the numbers can be 10 or greater, just treat it like software's version number, such as 1.32.1 is smaller than 1.33.0 $\endgroup$ – nopole Aug 1 at 13:16
  • $\begingroup$ and note that the first series [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 5],... is not lexicographic $\endgroup$ – nopole Aug 1 at 13:31
  • $\begingroup$ Yes, both are defining the order in a similar way, just that Knuth arranged the array elements in decreasing order and Wilf as arranged them in an increasing order. Then both of them use the same logic, element by element comparison to check which array "lexographically" comes first. This is where the ambiguity comes in. We are free to choose in which order do the array elements appear before comparing them to arrive at a lexographic ordering. $\endgroup$ – RandomPerfectHashFunction Aug 1 at 18:52
  • $\begingroup$ Also, the first one can be said to be in an lexographic order, if we compare the individual array elements from right to left. The bottom two compare from left to right. $\endgroup$ – RandomPerfectHashFunction Aug 1 at 18:54
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.