I’ve run into the following straightforward variant of lexicographic ordering, and am wondering if it has a standard name. I’ve been calling it the flipping lexicographic ordering, for evident reasons. I could also imagine it getting called the parity lexicographic ordering, but a brief search suggests that that’s used for some slightly different orderings. $\newcommand{\x}{\mathbf{x}} \newcommand{\y}{\mathbf{y}} \newcommand{\N}{\mathbb{N}} \newcommand{\fl}{\mathrm{fl}} \newcommand{\lfl}{\;\sqsubset^\fl\;}$

For sets $\x, \y \in \binom{\N}{m+1}$, write $\x = \{x_0 < \ldots < x_m\}$, $\y = \{y_0 < \ldots < y_m\}$.

Definition. $\x \lfl \y$ if $\x$ and $\y$ differ first in the $i$th place, and

  • $i$ is even, and $x_i < y_i$; or
  • $i$ is odd, and $y_i < x_i$. (This is the flip!)

As for ordinary lex, there’s also a nice inductive characterisation: Write $\x = \{x_0\} \cup \x^{\geq 1}$, and $\y = \{y_0\} \cup \y^{\geq 1}$, similarly to above. Then $\x \lfl \y$ if and only if either $x_0 < y_0$, or $x_0 = y_0$ and $\y^{\geq 1} \lfl \x^{\geq 1}$. (Again, note the flip.)

Does this ring any bells with anybody?

(Of course, $\lfl$ has obvious generalisations beyond $\binom{\N}{m+1}$; I’m sticking to that case here partly for definiteness, mainly since that’s the specific case I’m interested in.)

Background: I’ve been playing around with implementing the algorithms from Ross Street’s “The Algebra of Oriented Simplices” (and related papers) in Haskell/Agda, and this ordering turns out to make a computationally convenient stand-in for his $\lhd$ order, in places.

  • 6
    $\begingroup$ Reminds me of boustrophedon. $\endgroup$
    – Stephen S
    Feb 5, 2011 at 9:16
  • 2
    $\begingroup$ +1 for 'boustrophedon order' $\endgroup$
    – ndkrempel
    Feb 5, 2011 at 13:03
  • 3
    $\begingroup$ The first 4-letter word in the boustrophedonic dictionary is "waxy", since the only things that would beat it are $\{a < x < y < z\}$ and $\{a < w < x < z\}$, neither of which has any anagrams. $\endgroup$
    – Tracy Hall
    Feb 5, 2011 at 21:04

1 Answer 1


I found an example in the mathematical literature where the same ordering on words, and more specifically continued fractions, is called "alternating lexicographic" order. I guess that there are other examples too, and that this is name can be considered standard. The term "boustrophedonic order" also appears in the mathematical literature, but it seems to mean something different. The boustrophedonic order on the English alphabet is AZBYCXDW... . In my opinion, calling your ordering boustrophedonic is clever, but I think that "alternating lexicographic" is more consistent as well as more standard, since it is an alternating combination of the lexicographic and colexicographic (or lex and colex) orderings.

  • 3
    $\begingroup$ Maybe «boustrophedonic» is too clever :) $\endgroup$ Feb 5, 2011 at 20:53
  • $\begingroup$ Ah, thankyou very much — indeed, googling "alternating lexicographic" turns up quite a number of results, which (from a small sample) seem to describe the right ordering. This looks like the answer I was after. Although it now seems so pedestrian compared to ‘flipping’ and ‘boustrophedonic’… $\endgroup$ Feb 5, 2011 at 22:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .