Pairwise Order of a Sequence of Elements

In the very first post of this blog, I described a new measure of disorder which I called (\mathit{Amp}). I started its construction process by introducing what I dubbed the pairwise order of a sequence as follows:

A few days ago I went back to one of the simplest possible tools in the domain: a three-way comparator for two values:

[\mathit{comp}(x, y)= \begin{cases} 1 & \text{ if } x \lt y\ -1 & \text{ if } x \gt y\ 0 & \text{otherwise} \end{cases}]

Nothing ground-breaking so far, it’s similar to a negation of the sign function applied to the difference of two real numbers. Let’s apply it to all adjacent pairs of elements of a sequence of elements (X):

Still fairly boring if I’m being honest. We will call that new sequence the pairwise order of the sequence for the rest of the article. Today’s article is all about showing that this so-called pairwise order is, in fact, maybe not all that boring.

Definition(s) and properties

The definition above was spot-on when talking about the sign function and three-way comparisons. The “negation” part however felt a bit confusing upon rereading it: it seems to arbitrarily consider (x - y) instead of (y - x) without being explicit about it. I would rather describe it again as the sequence made of the sign function applied to the difference operator over a sequence of elements:

[\forall X_i \in \mathbb{R}, \mathit{Order}(X) = \langle \text{sgn } (\Delta X)_i \vert 1 \le i < \lvert X \rvert \rangle]

That new definition gets rid of the “negation” part, and the direction of the subtraction implicitly follows the definition of the difference operator. When I showed the article to a friend, she immediately described the pairwise order it as “discrete derivative”. It also accurately matches the intuition of the tool, even though I managed to write the whole thing without ever thinking of derivatives.

A few obvious properties of the pairwise order immediately emerge from its definition:

• Its size: (\lvert \mathit{Order}(X) \rvert = \lvert X \rvert - 1).
• A sorted sequence produces a pairwise order without any (-1) (and the opposite is true).
• A sequence sorted in reverse order produces a pairwise order without any (1) (the opposite is also true).
• A sequence of distinct elements produces a pairwise order without any (0).

Pairwise order and measures of disorder

If we have the pairwise order of a sequence (X), we can compute (\mathit{Amp}(X)). What’s interesting is that other measures of disorder can be redefined in terms of the pairwise order. Let’s take (\mathit{Runs}) for example. It is the number of steps-down in (X), which can trivially be redefined in terms of the pairwise order. Another such measure is (\mathit{Mono}), introduced in Sort Race. Intuitively, if (\mathit{Mono}(X) = k), then (X) is the concatenation of (k) monotonic lists.

All of those measures of disorder can be reduced to their effect on the pairwise order. Instead of trying to understand how they are affected by changes in the original sequence, we can analyze how they behave when adding or removing (-1), (0) or (1) from the pairwise order.

Equal elements in measures of disorder

Measures based on the pairwise order make the distinction between distinct and equal elements trivial. Sequences with equal elements produce a pairwise order which can contain (0) elements. We saw earlier that (\mathit{Runs}(X)) can be redefined as the number of (-1) in the pairwise order. This definition is valid regardless of whether the sequence contains equal elements or not. By using a function like std::unique, we can reduce the problem to comparing how changes to the pairwise order impact measures, entirely ignoring the (0) elements.

Conclusion

Over the course of the previous year, my vision of the pairwise order went from “fairly boring” to “wait, that’s actually a pretty cool tool”. Any two algorithms that are entirely based on the pairwise order of a sequence can be reduced to comparing changes to (-1), (0) and (1), thereby reducing the scope of the analysis.