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 this example, the list is sorted. It is assumed that the list can always be unambiguously entered into this form. The list is never cyclical.

Now, if possible, I need a compare comparator, which can get this form:

 x = [[4,1],[1,2],[2,3]] x.sort(compare) 

Suppose that the compare function returns one of two values, corresponding to more and less. Whether this is possible, and if so, depends on the sorting algorithm.

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

I wrote this in python, but my question is not specific.

Answer 1

This cannot be done in one pass, because the desired order is not a strict partial order . In particular, in order for the comparator to work, it must obey several properties:

• Irreflexivity: an element is never compared less than itself.
• Asymmetry: if a compares less than b, then b does not compare less than.
• Transitivity: if a compares less than b and b compares less than c, then c does not compare less than.

All three of these properties are violated in your case:

• [1, 1] compares less than itself, since you can chain [1, 1], [1, 1].
• Two elements can be mutually linked: [1, 4] chains with chains [4, 1] and [4, 1] with [1, 4].
• Transitivity is not satisfied: [1, 2] chains with chains [2, 3] and [2, 3] with [3, 4], but [1, 2] are not connected with [3, 4].

The best way to model your problem is to find the Euler path through a graph. The Euler path is a way to follow a series of links so that you never return a link or track all links. (If you ever had these “draw this shape without being distracted by the line or picking your pencils”), this is pretty much the same idea.) In your case, the links are pairs [a, b] and a chain through them coincides with the Euler path. Fortunately, there are many good efficient algorithms for finding Eulerian paths , and I think that they are exactly what you are looking for in this context.

Hope this helps!