Algorithme pour trier les paires de nombres

J'ai déjà posé cette question sur stackoverflow , mais c'est peut-être mieux adapté à ce site.

Le problème est:

J'ai N paires d'entiers non signés. J'ai besoin de les trier. Le vecteur de fin des paires doit être trié de façon non décroissante par le premier nombre de chaque paire et de manière non croissante par le second de chaque paire. Chaque paire peut avoir les premier et deuxième éléments échangés à tout moment. Parfois, il n'y a pas de solution, j'ai donc besoin de lever une exception.

Exemple:

in pairs:
1 5
7 1
3 8
5 6

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

^^ Sans échange de paires, il est impossible de construire la solution. Nous échangeons donc les paires (7, 1), (3, 8) et (5, 6) et construisons le résultat. ou

in pairs:
1 5
6 9

out:
not possible

Merci

Éditer:

Tom Sirgedas sur SO a proposé la meilleure solution . Il est vraiment facile à implémenter et fonctionne en O (log (n) * n). Merci à tous pour les réponses et l'intérêt. J'ai vraiment apprécié l'analyse mjqxxxx.

Supposons que deux paires et p 2 = ( a 2 , b 2 ) sont compatibles sans échange si elles peuvent être placées dans l'un ou l'autre ordre dans la liste triée sans échanger aucune. Cela est vrai si ( a 1 ≤ a 2 ∧ b 1 ≥ b 2 ) ou ( a 2 ≤ a 1 ∧ b 2 ≥ $p_1=(a_1,b_1)$$p_2=(a_2,b_2)$$(a_1 \le a_2 \wedge b_1 \ge b_2)$ . Notez que 1 et$(a_2 \le a_1 \wedge b_2 \ge b_1)$ et p 2 sont compatibles sans échange si et seulement s'ils sontcompatibles avec deux échanges (puisque l'ordre partiel défini satisfait p 1 ⪯ p 2 ≡ p ∗ 2 ⪯ p ∗ 1 , où ∗ désigne l'opération de swap). Enfin, p 1 et p 2 sontcompatibles avec un échanges'ils peuvent être placés dans l'un ou l'autre ordre dans la liste triée avec exactement l'un d'entre eux échangé. Cela est vrai si p ∗ p 2 sont compatibles sans échange. Dans les autres cas,$p_1$$p_2$$p_1 \preceq p_2 \equiv p_2^{*} \preceq p_1^{*}$$*$$p_1$$p_2$$p_1^{*}$$p_2$ et$p_1$ sont tout simplement incompatibles: ils ne peuvent pas satisfaire à la condition d'ordre indépendamment de leur état de swap.$p_2$

Le problème peut maintenant être résolu comme suit. Testez chaque paire de paires. Si une paire est incompatible, il n'y a pas de solution et nous pouvons lever une exception. Sinon, considérez le graphique avec des nœuds correspondant aux paires d'origine et des arêtes entre ces paires de nœuds qui ne sont pas compatibles avec un échange. Chacune de ces paires de nœuds doit avoir le même état de permutation dans toute liste correctement triée et, par conséquent, tous les nœuds de chaque composant connecté du graphique doivent avoir le même état de permutation. Nous devons déterminer si ces états de permutation à l'échelle du composant peuvent être attribués de manière cohérente. Testez toutes les paires de nœuds au sein de chaque composant connecté. Si une paire n'est pas compatible sans échange, il n'y a pas de solution et nous pouvons lever une exception. Testez maintenant toutes les paires de composants connectés (c'est-à-dire pour les composants $C_1$ et , testez toutes les paires de nœuds p 1 ∈ C 1 et p 2 ∈ C $C_2$$p_1 \in C_1$$p_2 \in C_2$). Nous savons que chaque paire de composants est au moins compatible avec un échange, mais certaines paires peuvent également être compatibles sans échange (car chaque paire de nœuds non connectés par un bord est au moins compatible avec un échange, et peut également être non). compatible avec swap). Considérons un graphe réduit avec des nœuds correspondant aux composants connectés et une arête entre deux nœuds si les composants correspondants ne sont pas compatibles sans échange. Il existe une solution au problème d'origine si et seulement si ce graphique est $2$ couleurs. S'il n'y en a pas $2$-la coloration, il n'y a pas de solution, et nous pouvons lever une exception. S'il y en a un, échangez tous les nœuds dans tous les composants d'une même couleur. Nous sommes maintenant garantis que deux nœuds sont compatibles sans échange, et nous pouvons donc trier correctement la liste des paires en utilisant l'ordre partiel défini.

Chaque étape de l'algorithme, et donc l'ensemble de l'algorithme, peut être effectuée en temps .$O(N^2)$

MISE À JOUR: Une construction beaucoup plus élégante est la suivante. Si une paire de paires n'est pas compatible sans échange, connectez les nœuds correspondants avec un bord (en les forçant à être de couleurs différentes dans n'importe quelle coloration 2). Si une paire de paires n'est pas compatible avec un échange, connectez les nœuds correspondants avec une chaîne de longueur 2 (en les forçant à être de la même couleur dans n'importe quelle coloration 2). Il n'y a de solution que si et seulement si le graphique résultant est bicolore. Pour construire une solution à partir d'une coloration bleu-rouge du graphique, permutez uniquement les paires dont les nœuds correspondants sont bleus, puis triez la liste résultante.

Soit X (a, b) la variable binaire indiquant si la paire (a, b) doit être permutée. Considérons tout couple de paires distinctes (a, b) et (c, d) et écrivez une contrainte binaire sur les variables X (a, b) et X (c, d) qui est satisfaite si et seulement si les deux paires sont en l'ordre correct après avoir effectué les swaps indiqués par X (a, b) et X (c, d), respectivement. La conjonction de toutes ces contraintes binaires est une formule 2-SAT dans n variables et clauses O (n ^ 2) qui est satisfaisante si et seulement si le problème d'origine a une solution. Cela peut être vérifié dans le temps O (n ^ 2).

Quant à la solution d'origine, il suffit de noter que toutes les contraintes sont de la forme X (a, b) = X (c, d) ou X (a, b)! = X (c, d) (ou bien X (a, b) = constant), donc un simple algorithme "fusionner et vérifier la bipartité" fonctionne:

Commencez avec chaque X étant le représentant de l'ensemble ne contenant que lui-même; puis pour chaque paire (X, Y) telle que X = Y est une contrainte, fusionnez les composants auxquels appartiennent X et Y; et enfin vérifier que le graphe contracté, où chaque composant est un sommet et une arête rejoint les composants contenant X et Y si la relation X! = Y doit tenir, est bipartite.