<p>Say that two pairs $p_1=(a_1,b_1)$ and $p_2=(a_2,b_2)$ are <em>no-swap compatible</em> if they can be placed in either order in the sorted list without swapping either one.  This is true if either $(a_1 \le a_2 \wedge b_1 \ge b_2)$ or $(a_2 \le a_1 \wedge b_2 \ge b_1)$.  Note that $p_1$ and $p_2$ are no-swap compatible if and only if they are <em>two-swap compatible</em> (since the partial order defined satisfies $p_1 \preceq p_2 \equiv p_2^{*} \preceq p_1^{*}$, where $*$ denotes the swap operation).  Finally, $p_1$ and $p_2$ are <em>one-swap compatible</em> if they can be placed in either order in the sorted list with exactly one of them swapped.  This is true if $p_1^{*}$ and $p_2$ are no-swap compatible.  In the remaining cases, $p_1$ and $p_2$ are simply incompatible: they cannot satisfy the order condition regardless of their swap state.</p>

<p>The problem can now be solved as follows.  Test every pair of pairs.  If any pair is incompatible, there is no solution, and we can throw an exception.  Otherwise, consider the graph with nodes corresponding to the original pairs, and edges between those pairs of nodes that are <em>not</em> one-swap compatible.  Each such pair of nodes must have the same swap state in any properly sorted list, and therefore all nodes in each connected component of the graph must have the same swap state.  We need to determine if these component-wide swap states can be consistently assigned.  Test all pairs of nodes within each connected component.  If any pair is not no-swap compatible, there is no solution, and we can throw an exception.  Now test all pairs of connected components (i.e., for components $C_1$ and $C_2$, test all pairs of nodes $p_1 \in C_1$ and $p_2 \in C_2$).  We know that each pair of components is at least one-swap compatible, but some pairs may also be no-swap compatible (because each pair of nodes not connected by an edge is at least one-swap compatible, and may also be no-swap compatible).  Consider a reduced graph with nodes corresponding to the connected components, and an edge between two nodes if the corresponding components are <em>not</em> no-swap compatible.  There is a solution to the original problem if and only if this graph is $2$-colorable.  If there is no $2$-coloring, there is no solution, and we can throw an exception.  If there is one, then swap all nodes in all components of a single color.  We are now guaranteed that any two nodes are no-swap compatible, and so we can properly sort the list of pairs using the defined partial order.</p>

<p>Each step in the algorithm, and hence the entire algorithm, can be performed in $O(N^2)$ time.</p>

<hr>

<p>UPDATE: A much more elegant construction is the following.  If a pair of pairs is not no-swap compatible, connect the corresponding nodes with an edge (forcing them to be different colors in any 2-coloring).  If a pair of pairs is not one-swap compatible, connect the corresponding nodes with a chain of length 2 (forcing them to be the same color in any 2-coloring).  There is a solution if and only if the resulting graph is 2-colorable.  To construct a solution from a blue-red coloring of the graph, swap just those pairs whose corresponding nodes are blue, then sort the resulting list.</p>

CC BY-SA 2.5
2011-03-17T13:09:20.907Z
Thank you very much for you answer. I really enjoyed reading it. Check the answer proposed on SO. Although it doesn't rely on graph theory which means it is less interesting then your elegant solution :), it is faster. Thank you for your time.
Klark
CC BY-SA 2.5
2011-03-16T15:05:57.817Z
2011-03-16T19:02:49.423Z
2011-03-16T19:02:49.423Z
mjqxxxx
<p>Let X(a, b) denote the binary variable indicating whether pair (a, b) should
be swapped.  Consider any couple of distinct pairs (a, b) and (c, d) and write
a binary constraint on the variables X(a, b) and X(c, d) that is satisfied if
and only if the two pairs are in the correct order after performing the swaps
indicated by X(a, b) and X(c, d), respectively. The conjunction of all such
binary constraints is a 2-SAT formula in n variables and O(n^2) clauses
which is satisfiable if and only if the original problem has a solution. This
can be checked in time O(n^2).</p>

<hr>

<p>As for the original solution, just note that all constraints are of the form
X(a, b) = X(c, d) or X(a, b) != X(c, d) (or else X(a, b) = constant), so a 
simple "merge and check for bipartiteness" algorithm works:</p>

<p>Start with each X being the representative for the set containing only itself; then for every pair (X, Y) such that X = Y is a constraint, merge the components to which X and Y belong; and finally check that the contracted graph, where each component is one vertex and some edge joins the components containing X and Y if the relationship X != Y must hold, is bipartite.</p>

CC BY-SA 2.5
2011-03-16T15:55:57.570Z
"$X(a,b)=X(c,d)$ must hold" is not an equivalence relation on pairs, I don't think.
mjqxxxx
CC BY-SA 2.5
2011-03-16T16:00:47.240Z
So? The equivalence relation here is the transitive closure of the relation (a, b) R (c, d) iff a < c and b > d or viceversa. Maybe I was not completely explicit, but this should be obvious from my answer.
david
CC BY-SA 2.5
2011-03-16T16:06:40.760Z
More accurately, "$a<c \wedge b>d$" is not an equivalence relation on pairs, and nor does it imply that $X(a,b)$ must be the same as $X(c,d)$ (though it does imply that they could be the same).  For instance, consider the pairs $(1,10)$, $(2,5)$, and $(3,7)$.
mjqxxxx
CC BY-SA 2.5
2011-03-16T16:15:03.950Z
You're confused. I never claimed that was an equivalence relation. But its transitive and reflexive closure is, by definition.
david
CC BY-SA 2.5
2011-03-16T16:32:24.013Z
On the other hand you're right in pointing out it does not necessarily imply X(a, b) = X(c, d), I was a bit hasty with
the constraint writing. Still it can be fixed; the `laziest'' way to see this is that the set of constraints of the original problem can be written as a 2-SAT formula over the variables X(a, b), so it can be solved in O(n^2) time. I can edit my original answer but since there's already another answer I'm not sure it's worth it.
david
CC BY-SA 2.5
2011-03-16T16:48:18.120Z
I edited my answer to correct the bug.
david
CC BY-SA 2.5
2011-03-16T17:43:39.820Z
How is it a 2-SAT formula?  The clauses that are not tautologies or contradictions seem to be either $X\equiv Y$ or $X\equiv \neg Y$.
mjqxxxx
CC BY-SA 2.5
2011-03-16T19:23:58.720Z
Are you kidding? First of all, *any* relationship between just two variables can be expressed as a 2-SAT formula.  For example, X = Y is the same as (X implies Y) and (not X implies not Y).

On the other hand, if all constraints are indeed of the form X = Y or X = not Y, then there's no need to run the 2SAT algorithm at all: the simpler "merge and check for bipartiteness" algorithm I described earlier works.
david
CC BY-SA 3.0
2011-03-16T15:29:02.930Z
2011-11-30T10:48:27.210Z
2011-11-30T10:48:27.210Z
david
<p>I already asked this question on <a href="https://stackoverflow.com/questions/5323941/algorithm-to-sort-pairs-of-numbers">stackoverflow</a>, but maybe it is better suited for this site.</p>

<p>The problem is:</p>

<p>I have N pairs of unsigned integerers. I need to sort them. The ending vector of pairs should be sorted nondecreasingly by the first number in each pair and nonincreasingly by the second in each pair. Each pair can have the first and second elements swapped at any point.  Sometimes there is no solution, so I need to throw an exception then.</p>

<p>Example:</p>

<pre><code>in pairs:
1 5
7 1
3 8
5 6

out pairs:
1 7     &lt;-- swapped
1 5     
6 5     &lt;-- swapped
8 3     &lt;-- swapped
</code></pre>

<p>^^ Without swapping pairs it is impossible to build the solution. So we swap pairs (7, 1), (3, 8) and (5, 6) and build the result.
or</p>

<pre><code>in pairs:
1 5
6 9

out:
not possible
</code></pre>

<p>Thanks</p>

<p><strong>edit:</strong></p>

<p>Tom Sirgedas on SO proposed the best <a href="https://stackoverflow.com/questions/5323941/algorithm-to-sort-pairs-of-numbers/5333242#5333242">solution</a>. It is really easy to implement and works in O(log(n) * n). Thank you all for the answers and interest. I really enjoyed mjqxxxx analysis.</p>

CC BY-SA 2.5
2011-03-16T12:43:23.430Z
Interesting problem. Without the swapping it's straightforward, but with swapping it is not clear that a unique solution exists.
Dave Clarke
CC BY-SA 2.5
2011-03-16T13:55:25.350Z
Unique solution doesn't always exist for sure. I.e. (1, 10), (5, 6). Both (1, 10), (5, 6) and (1, 10), (6, 5) are correct.
Klark
CC BY-SA 2.5
2011-03-16T13:59:14.240Z
Next time please include a link.  http://stackoverflow.com/questions/5323941/algorithm-to-sort-pairs-of-numbers
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-16T14:30:27.307Z
Did this problem arise in some application, or just out of curiosity?
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-16T14:36:28.607Z
One friend of mine got it as paper-test-interview question. So I guess it is just out of curiosity :)
Klark
CC BY-SA 2.5
2011-03-16T15:32:42.253Z
(1) Klark, Thank you for the reply.  (2) I do not think that this question is a research-level question, but I guess that it is the scope that should be changed.  I started a [discussion on meta](http://meta.cstheory.stackexchange.com/questions/1066/we-should-stop-claiming-that-this-website-is-research-level).
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-16T21:52:44.143Z
Virtual vote to close (I've clarified my reasons on the meta discussion)
Suresh Venkat
CC BY-SA 3.0
2011-12-01T07:14:55.543Z
"Vote to close" AND "start a bounty"? Which way is the post bound?
Kris
<ds.algorithms><sorting>
Algorithm to sort pairs of numbers
Klark
# Algorithm to sort pairs of numbers

(Asked by: username_0 on 2011-03-16)

I already asked this question on stackoverflow, but maybe it is better suited for this site.
The problem is:
I have N pairs of unsigned integerers. I need to sort them. The ending vector of pairs should be sorted nondecreasingly by the first number in each pair and nonincreasingly by the second in each pair. Each pair can have the first and second elements swapped at any point.  Sometimes there is no solution, so I need to throw an exception then.
Example:
in pairs:
1 5
7 1
3 8
5 6

out pairs:
1 7     <-- swapped
1 5     
6 5     <-- swapped
8 3     <-- swapped

^^ Without swapping pairs it is impossible to build the solution. So we swap pairs (7, 1), (3, 8) and (5, 6) and build the result.
or
in pairs:
1 5
6 9

out:
not possible

Thanks
edit:
Tom Sirgedas on SO proposed the best solution. It is really easy to implement and works in O(log(n) * n). Thank you all for the answers and interest. I really enjoyed mjqxxxx analysis.

**Tags:** ds.algorithms, sorting
> **Comments:**
> **username_1**: Interesting problem. Without the swapping it's straightforward, but with swapping it is not clear that a unique solution exists.  
> **username_0**: Unique solution doesn't always exist for sure. I.e. (1, 10), (5, 6). Both (1, 10), (5, 6) and (1, 10), (6, 5) are correct.  
> **username_2**: Next time please include a link.  http://stackoverflow.com/questions/5323941/algorithm-to-sort-pairs-of-numbers  
> **username_2**: Did this problem arise in some application, or just out of curiosity?  
> **username_0**: One friend of mine got it as paper-test-interview question. So I guess it is just out of curiosity :)  
> **username_2**: (1) Klark, Thank you for the reply.  (2) I do not think that this question is a research-level question, but I guess that it is the scope that should be changed.  I started a [discussion on meta](http://meta.cstheory.stackexchange.com/questions/1066/we-should-stop-claiming-that-this-website-is-research-level).  
> **username_3**: Virtual vote to close (I've clarified my reasons on the meta discussion)  
> **username_4**: "Vote to close" AND "start a bounty"? Which way is the post bound?  

---

## 2 answers

### Answer by username_5 on 2011-03-16. Score: 8

Say that two pairs $p\_1=(a\_1,b\_1)$ and $p\_2=(a\_2,b\_2)$ are *no-swap compatible* if they can be placed in either order in the sorted list without swapping either one. This is true if either $(a\_1 \le a\_2 \wedge b\_1 \ge b\_2)$ or $(a\_2 \le a\_1 \wedge b\_2 \ge b\_1)$. Note that $p\_1$ and $p\_2$ are no-swap compatible if and only if they are *two-swap compatible* (since the partial order defined satisfies $p\_1 \preceq p\_2 \equiv p\_2^{\*} \preceq p\_1^{\*}$, where $\*$ denotes the swap operation). Finally, $p\_1$ and $p\_2$ are *one-swap compatible* if they can be placed in either order in the sorted list with exactly one of them swapped. This is true if $p\_1^{\*}$ and $p\_2$ are no-swap compatible. In the remaining cases, $p\_1$ and $p\_2$ are simply incompatible: they cannot satisfy the order condition regardless of their swap state.

The problem can now be solved as follows. Test every pair of pairs. If any pair is incompatible, there is no solution, and we can throw an exception. Otherwise, consider the graph with nodes corresponding to the original pairs, and edges between those pairs of nodes that are *not* one-swap compatible. Each such pair of nodes must have the same swap state in any properly sorted list, and therefore all nodes in each connected component of the graph must have the same swap state. We need to determine if these component-wide swap states can be consistently assigned. Test all pairs of nodes within each connected component. If any pair is not no-swap compatible, there is no solution, and we can throw an exception. Now test all pairs of connected components (i.e., for components $C\_1$ and $C\_2$, test all pairs of nodes $p\_1 \in C\_1$ and $p\_2 \in C\_2$). We know that each pair of components is at least one-swap compatible, but some pairs may also be no-swap compatible (because each pair of nodes not connected by an edge is at least one-swap compatible, and may also be no-swap compatible). Consider a reduced graph with nodes corresponding to the connected components, and an edge between two nodes if the corresponding components are *not* no-swap compatible. There is a solution to the original problem if and only if this graph is $2$-colorable. If there is no $2$-coloring, there is no solution, and we can throw an exception. If there is one, then swap all nodes in all components of a single color. We are now guaranteed that any two nodes are no-swap compatible, and so we can properly sort the list of pairs using the defined partial order.

Each step in the algorithm, and hence the entire algorithm, can be performed in $O(N^2)$ time.

---

UPDATE: A much more elegant construction is the following. If a pair of pairs is not no-swap compatible, connect the corresponding nodes with an edge (forcing them to be different colors in any 2-coloring). If a pair of pairs is not one-swap compatible, connect the corresponding nodes with a chain of length 2 (forcing them to be the same color in any 2-coloring). There is a solution if and only if the resulting graph is 2-colorable. To construct a solution from a blue-red coloring of the graph, swap just those pairs whose corresponding nodes are blue, then sort the resulting list.

> **Comments:**
> **username_0**: Thank you very much for you answer. I really enjoyed reading it. Check the answer proposed on SO. Although it doesn't rely on graph theory which means it is less interesting then your elegant solution :), it is faster. Thank you for your time.  

---

### Answer by username_6 on 2011-03-16. Score: 3

Let X(a, b) denote the binary variable indicating whether pair (a, b) should
be swapped. Consider any couple of distinct pairs (a, b) and (c, d) and write
a binary constraint on the variables X(a, b) and X(c, d) that is satisfied if
and only if the two pairs are in the correct order after performing the swaps
indicated by X(a, b) and X(c, d), respectively. The conjunction of all such
binary constraints is a 2-SAT formula in n variables and O(n^2) clauses
which is satisfiable if and only if the original problem has a solution. This
can be checked in time O(n^2).

---

As for the original solution, just note that all constraints are of the form
X(a, b) = X(c, d) or X(a, b) != X(c, d) (or else X(a, b) = constant), so a
simple "merge and check for bipartiteness" algorithm works:

Start with each X being the representative for the set containing only itself; then for every pair (X, Y) such that X = Y is a constraint, merge the components to which X and Y belong; and finally check that the contracted graph, where each component is one vertex and some edge joins the components containing X and Y if the relationship X != Y must hold, is bipartite.

> **Comments:**
> **username_5**: "$X(a,b)=X(c,d)$ must hold" is not an equivalence relation on pairs, I don't think.  
> **username_6**: So? The equivalence relation here is the transitive closure of the relation (a, b) R (c, d) iff a < c and b > d or viceversa. Maybe I was not completely explicit, but this should be obvious from my answer.  
> **username_5**: More accurately, "$a<c \wedge b>d$" is not an equivalence relation on pairs, and nor does it imply that $X(a,b)$ must be the same as $X(c,d)$ (though it does imply that they could be the same).  For instance, consider the pairs $(1,10)$, $(2,5)$, and $(3,7)$.  
> **username_6**: You're confused. I never claimed that was an equivalence relation. But its transitive and reflexive closure is, by definition.  
> **username_6**: On the other hand you're right in pointing out it does not necessarily imply X(a, b) = X(c, d), I was a bit hasty with the constraint writing. Still it can be fixed; the `laziest'' way to see this is that the set of constraints of the original problem can be written as a 2-SAT formula over the variables X(a, b), so it can be solved in O(n^2) time. I can edit my original answer but since there's already another answer I'm not sure it's worth it.  
> **username_6**: I edited my answer to correct the bug.  
> **username_5**: How is it a 2-SAT formula?  The clauses that are not tautologies or contradictions seem to be either $X\equiv Y$ or $X\equiv \neg Y$.  
> **username_6**: Are you kidding? First of all, *any* relationship between just two variables can be expressed as a 2-SAT formula.  For example, X = Y is the same as (X implies Y) and (not X implies not Y).  On the other hand, if all constraints are indeed of the form X = Y or X = not Y, then there's no need to run the 2SAT algorithm at all: the simpler "merge and check for bipartiteness" algorithm I described earlier works.  

---

