Talk:Lexicographical order

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Linguistics / Applied Linguistics  (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Linguistics, a collaborative effort to improve the coverage of Linguistics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
Taskforce icon
This article is supported by the Applied Linguistics Task Force.
 


Untitled[edit]

The term "dictionary order" is a misnomer: most dictionaries are not in simple lexicographical order. -- The Anome 08:18, 10 Apr 2004 (UTC)

Nevertheless, "dictionary order" is standard mathematical terminology, regardless of whether it completely conforms to the ordinary use of the term. BTW, I see no reason why the number of sets cannot be generalised to range over any ordinal number, (e.g. here it is given for a finite ordinal, but the definition for countable number seems obvious, and the definition for an arbitrary ordinal seems like it should make sense.) Revolver 23:34, 7 Jul 2004 (UTC)

An important property of the lexicographical order is that it preserves well-orders, that is, if A and B are well-ordered sets, then the product set A × B with the lexicographical order is also well-ordered.

Isn't this just ordinal multiplication, with the order of A and B reversed? If this is the case, is it possible to define ordinal multiplication where the factors themselves are indexed by an ordinal? I've seen cardinal multiplication defined for indexed families, but not ordinal. Revolver 23:46, 7 Jul 2004 (UTC)
Ah, I think I see where I screwing up. It is true (I checked a set theory book) that the product of two ordinals is the dictionary ordering on the cartesian product, with the order of factors reversed. And, it also seems true (I haven't gone through the details) that if you have a family of totally ordered sets, indexed by an ordinal number, then you could define the dictionary ordering on that family, and it would again turn out to be a totally ordered set. (Define: if two elements aren't equal, then they disagree in a coordinate, these coordinates are indexed by an ordinal, so the set of all coordinates where they disagree is a nonempty set, has a least element, compare at that coordinate.) In particular, you could do this for a family of well-ordered sets, but in this case, the dictionary order might not be well-ordered. (Consider the dictionary order on 2, 2, 2, 2, ..., where the index ordinal is w. Then 1, 1, 1, 1, 1, ...; 1, 0, 1, 1, 1 ; ..., 1, 0, 0, 1, 1, ...; etc. is a strictly decreasing sequence in 2, 2, 2, ..., so it can't be well-ordered.) Revolver 01:10, 8 Jul 2004 (UTC)


There is a problem here with how the ordering is extended to products of different lengths. (For simplicity I'll assume we have a fixed alphabet \Sigma = \{a,b\} and are ordering strings of \Sigma^*.) The standard dictionary order is what (Sims 94, Computation With Finitely Presented Groups) calls the left-right-lexicographic order. This is not a well-order, since if a < b then b > ab > aab > aaab > ... is an infinite decreasing sequence of elements. In general strings of fixed length do preserver the well-ordering property but by using the 'space padding' method described in the article to extend the definition to the LR-lex order the property no longer holds.

There, is, however, a natural ordering on \Sigma^* called length-plus-lexicographic order. If w1 = x1x2...xi and w2 = y1y2...yj then w1 < w2 iff i<j or i=j and w1 << w2 where << is the lexicographical order on \Sigma^k. To see how these orders differ, consider the following examples.

Set: {b,ab,aab,aaab,...}

  • Left-right-lexicographic ordering: b > ab > aab > aaab > ...
  • Length-plus-lexicographic ordering: b < ab < aab < aaab < ...

Set: {a,b,aa,bb,abab}

  • Left-right-lexicographic ordering: a < aa < abab < b < bb
  • Length-plus-lexicographic ordering: a < b < aa < bb < abab

There is also a wreath product of orderings on sets that preserves the well-ordering property but it is a bit involved to explain here. Maybe at some point in the future I'll take a shot at rewriting this page to include these definitions. TooMuchMath 22:14, 26 April 2006 (UTC)

That would be nice. Another observation is that these are all equivalent for any set with the prefix property. Calbaer 22:51, 6 November 2006 (UTC)
I added a paragraph on the ordering of strings, in which I also mention what you call Length-plus-lexicographic ordering; I found a stub (Shortlex order) which describes it. Let us expand it! I'll start by adding the alternate names Length-plus-lexicographic and Radix order - that's the name I knew for it. --fudo (questions?) 20:19, 25 February 2007 (UTC)
Sipser's Introduction to the Theory of Computation says, "The lexicographic ordering of strings is the same as the familiar dictionary ordering, except that shorter strings precede longer strings. Thus the lexicographic ordering of all strings over the alphabet {0,1} is {empty,0,1,00,01,10,11,000,...}." That would seem to be the Shortlex order ordering. Maybe something should be said noting that the definition is not universal. Steve Checkoway (talk) 23:22, 8 July 2008 (UTC)

Removed C++ string comparison[edit]

Why did we have a C++ string comparison function here? It is, at most, marginally related to the topic of this article. Moreover, why case insensitive? Lexicographic orders have nothing to do (are ortogonal) to being case (in)sensitive. Since, anyway, Wikipedia is not a collection of "how-to"s, I've decided to remove this section. --NavarroJ 11:21, 16 September 2006 (UTC)

Accessible intro[edit]

There should be a more accessible introduction, which gives an example that older elementary school children (and for that matter high school students and non-mathematically inclined adults) can understand. -- Beland 06:21, 23 September 2007 (UTC)

Second the motion... think of me as an intelligent but uninformed reader. As it stands now it says: "Given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as (a,b) ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′)." I feel like a bunch of knives are being tossed at me to catch. A, B, got 'em. Now here's a and b, what are lower case a,b? part of sets A or B or something else? a and b are not defined! And what is the significance of A and B being partially ordered? Does this whole thing fall apart if they are mostly ordered, or completely unordered, or what? And what on earth is this about a Cartesian product? What does multiplication have to do with putting a series in order, and how can two sets be multiplied, partially ordered or otherwise? Numerous puzzles here, all of which require research before I can solve them, and only then can I learn what I came here to learn. I suggest that if you can't express it clearly you might just not understand it yourself.Friendly Person (talk) 20:54, 3 May 2011 (UTC)
I have split off ==Definition==.--Patrick (talk) 22:11, 3 May 2011 (UTC)

Representability[edit]

A word about lexicographical orders being nonrepresentable by real functions in general? —Preceding unsigned comment added by 202.36.179.66 (talk) 02:56, 28 August 2009 (UTC)

Merge Colexicographical order to Lexicographical order[edit]

Colexicographical order should be merged into Lexicographical order. I don't think Colexicographical order can ever be more than a dictionary definition; anything of encyclopedic value that can be said in one article can also be said in the other.

The "Definition" section would be a good place to introduce the term. More material could be put in the "Reverse lexicographic order" section if necessary. Melchoir (talk) 02:03, 18 May 2011 (UTC)

Compare with Orderings at OEIS-Wiki[edit]

At the moment this article states that reverse lex. order is that of a rhyming dictionary. But Orderings at OEIS-Wiki states that reverse lex. order is lex. order upside down. Reading the OEIS article I would say that colexicographical order is that of a rhyming dictionary. Lipedia (talk) 15:10, 1 January 2012 (UTC)

Image Label Accuracy[edit]

On the left side the smaller numbers are have a dark background, on the right side the bigger numbers.

Are the image labels accurate? The 2 labels above the very left grids of red and white squares seem backwards. The labels above the circled numbers all make sense, and on the right side of the image, the labels for the red and white squares match the labels above the circled numbers, but on the left they're switched --Yoda of Borg (talk) 19:16, 5 July 2012 (UTC)

Yes, it looks like there's something wrong. On the right-hand side as well, according to my understanding. The various instances of the word "Rev" seem to be misplaced. Nothing we can immediately do, since the image is not editable, but unless someone can enlighten us as to its correctness, I think it ought to be removed. Victor Yus (talk) 07:26, 6 July 2012 (UTC)

I made it like that for a purpose. You can see that the colors in the arrangements of 20x3 balls on the left and on the right are horizontally reflected, although the numbers are not. So we can see how colex order is related to lex order. The similarity between lex and colex order is not easily shown, and this is one way to do it. However: The actual information are the white numbers. The bluish colors are just a background to make the pattern comprehensible. Lipedia (talk) 09:30, 6 July 2012 (UTC)

But why does it say "Rev Lex" above the top left chart, and "Lex" above the bottom left one? Shouldn't these be the other way round? Victor Yus (talk) 11:01, 6 July 2012 (UTC)

Left side:
When the actual triples (caption in gray) are in lex order, the corresponding binary vectors (red caption) are in revlex order.
Right side:
When the actual triples are in colex order, the corresponding binary vectors are in are in colex order as well.
Compare:
v:Lexicographic and colexicographic order#Permutations - When permutations are in revcolex order the corresponding inversion vectors are in colex order.
Lipedia (talk) 12:29, 6 July 2012 (UTC)

OK, I see, I guess it's correct. But for this to make any sense, it all needs to be explained in the article. There seems to be nothing in the article about binary vectors, or how they might "correspond" to subsets (and in fact I don't think it's strictly subsets that are being ordered here, but ordered triples). I also agree with the proposal to merge the article on colex order with this one. And there seems to be inconsistency in the definition of reverse lex order as given in the article and as used here. Lots to sort out. Victor Yus (talk) 10:15, 7 July 2012 (UTC)

Misleading comma/phrasing[edit]

The article says (paraphrased) the word A comes before B "if and only if the first a_i, which is different from b_i, comes before b_i in the alphabet.

This could be misinterpreted as implying a_1!=b_1 due to the comma appearing before "which," when the intention was clearly to define i to be the least i such that a_i!=b_i. It seems like bad practice to place the definition of a variable inside what one might interpret as an appositive phrase, though with that interpretation i would be appearing without any definition whatsoever. Jaycob Coleman (talk) 01:37, 26 November 2013 (UTC)

I attempted to clarify it. -- Elphion (talk) 04:02, 26 November 2013 (UTC)