14
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Interesting problem. Without the swapping it's straightforward, but with swapping it is not clear that a unique solution exists. $\endgroup$ – Dave Clarke Mar 16 '11 at 12:43
  • 2
    $\begingroup$ 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. $\endgroup$ – Klark Mar 16 '11 at 13:55
  • 4
    $\begingroup$ Next time please include a link. stackoverflow.com/questions/5323941/… $\endgroup$ – Tsuyoshi Ito Mar 16 '11 at 13:59
  • 2
    $\begingroup$ One friend of mine got it as paper-test-interview question. So I guess it is just out of curiosity :) $\endgroup$ – Klark Mar 16 '11 at 14:36
  • 3
    $\begingroup$ (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. $\endgroup$ – Tsuyoshi Ito Mar 16 '11 at 15:32
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Klark Mar 17 '11 at 13:09
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "$X(a,b)=X(c,d)$ must hold" is not an equivalence relation on pairs, I don't think. $\endgroup$ – mjqxxxx Mar 16 '11 at 15:55
  • $\begingroup$ 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. $\endgroup$ – david Mar 16 '11 at 16:00
  • 1
    $\begingroup$ 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)$. $\endgroup$ – mjqxxxx Mar 16 '11 at 16:06
  • 1
    $\begingroup$ 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$. $\endgroup$ – mjqxxxx Mar 16 '11 at 17:43
  • 1
    $\begingroup$ 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. $\endgroup$ – david Mar 16 '11 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.