![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
![]() | This article contains a translation of Code de Lehmer from fr.wikipedia. |
While this article used to be a redirect to a section of Permutation, it has now been made an independent article based on a translation of the French WP article on the subject. While I see not much wrong with that (provided the article is rapidly cleaned up, notably the references), I should note that the description now contradicts the one in the permutation article, in two respects: the values are taken to start at 1 rather than 0, and they count at position i the inversions {i,j} with j≤i (left inversions at i) rather than with j>i (right inversion at i).
I think there is agreement over the fact that there are basically 4 variations of the concept (listed by Knuth in exercise 5.1.1−7 (p. 19) of volume III of The art of computer programming, which number can be doubled by counting from 1 rather than from 0, and once more by complementary counting: counting non-inversions rather than inversions, so that the identity gives the highest possible values rather than the lowest), and that " inversion table" and "Lehmer code" both refer to one of those variations. However, while it is mathematically not very interesting which one is actually meant, I think WP should be clear and coherent about it (especially since people no doubt will use it as a quick reference). I don't think that there is universal agreement about which variation should be called Lehmer code; I would tend to say that the original Lehmer article should be decisive, unless a coherent (maybe different) convention is established since. Unfortunately the original article seems obscure and hard to get at (the AMS does not seem to distribute it anymore in any form), and Knuth (which I would consider an authoritative reference) refuses to use the term Lehmer code (for good historic reasons, I think), and there is no universal agreement about that term in modern usage. Some non-authoritative (but non-WP)references I found by Google:
I'll stop my list here. Actually, I started the list with the intention to show the lack of agreement, but there appears to be a fairly strong tendency to the notion described in the Permutation article (counting inversions to the right), which I will now call the majority definition. Also those using a different convention do not seem to agree among each other.
One word about the factorial number system. It is not the same as Lehmer code, since it encodes (large) numbers rather than permutations by sequences of small numbers. However such a large number is easily (and often) associated to the corresponding permutation in the lexicographically ordered list, and under this correspondence the factorial number system (with the most significant digit on the left, as is usual for number systems) matches the majority definition of Lehmer code. Therefore I would count item 6 on the above list as support for the majority. Also this point of view allows giving a property that singles out the majority definition among all other variants: it is the only variant for which the lexicographic ordering on permutations corresponds to the lexicographic ordering of the corresponding codes. (Well actually its own variant that counts from 1 also has this property, but apart from being used by nobody as far as I know, such variants does not correctly count the total number of inversions, which is a good reason to count from 0.)
I would propose:
In fact the three propositions are independent, so even if one prefers to keep the name "Lehmer code", I think it's definition should be changed. Marc van Leeuwen ( talk) 13:07, 8 October 2011 (UTC)
The above, immensely valuable comment, was made while the translation of the article was still a work in progress, with more focus on translating and formating than on the intrisic concepts. This initial phase being now completed, I'm all in favor of consolidating the scientific accuarcy.
The question of (count from 0 | count from 1) is now addressed, albeit briefly, in (now clean) [ #3] - Maybe it could use its own paragraph rather than a mere footnote ? Also a footnote to a footnote was lost in translation : Knuth is cited as citing one Marshall Hall on his choice of the phrase "invertion table" over "Lehmer code". Maybe the complete Hall reference shall be retrieved and included here ?
And of course, I feel that the main goal should be to tie the (factoradic, permutation, Lehmer code) articles in a consistent and readable triptic. — Preceding unsigned comment added by Herix ( talk • contribs) 14:11, 8 October 2011 (UTC)
The article currently claims this was named for Derrick Henry Lehmer, but in the article on the father of D. H. Lehmer, Derrick Norman Lehmer, he is credited. So was this named for the father, for the son, or for both? / 80.71.135.103 ( talk) 11:12, 4 September 2013 (UTC)