A comparator that finds chains

Question

I have a list of pairs like

[[4,1],[1,2],[2,3]]

The idea is to sort them so that the second index of the first node matches the first of the second. In the example, the list is sorted. It is assumed that the list can always be put uniquely into this form. The list is never cyclic.

Now, if it is possible I want a comparator compare that can obtain this form by:

x = [[4,1],[1,2],[2,3]]

x.sort(compare)

Let's assume the function compare returns one of two values corresponding to "bigger", and "smaller". Is this even possible, and if it is, does it depend on the sorting algorithm.

If it is not possible, is it doable with two passes (perhaps with different comparators) or any fixed number of passes.

I've written this in python, but my question is not intended to be specific.

Answer 1

It is not possible to do this in one pass because the ordering you want is not a strict partial order. Specifically, in order for a comparator to work, it needs to obey several properties:

1. Irreflexivity: An element never compares less than itself.
2. Asymmetry: If a compares less than b, then b does not compare less than a.
3. Transitivity: If a compares less than b and b compares less than c, then c does not compare less than a.

All three of these properties are violated in your case:

1. [1, 1] compares less than itself, since you can chain [1, 1], [1, 1].
2. Two elements can be mutually chained: [1, 4] chains with [4, 1] and [4, 1] chains with [1, 4].
3. Transitivity does not hold: [1, 2] chains with [2, 3] and [2, 3] chains with [3, 4], but [1, 2] does not chain with [3, 4].

A better way of modeling your problem is trying to find an Eulerian path through a graph. An Eulerian path is a way of following a series of links so that you never retrace a link and such that all links are traced out. (If you ever had those "draw this figure without retracing a line or picking up your pencil" puzzles, it's pretty much the same idea.) In your case, the links are the pairs [a, b], and a chain through them is the same as an Eulerian path. Fortunately, there are many good, efficient algorithms for finding Eulerian paths, and I think they're exactly what you are looking for in this context.

Hope this helps!