Nombre minimum de transpositions pour trier une liste

En essayant de concevoir mon propre algorithme de tri, je cherche le benchmark optimal auquel je peux le comparer. Pour un ordre non trié des éléments A et un ordre trié B , quel est un moyen efficace de calculer le nombre optimal de transpositions pour passer de A à B ?

Une transposition est définie comme la commutation de la position de 2 éléments dans la liste, donc par exemple

1 2 4 3

a une transposition (transposition 4 et 3) pour le rendre

1 2 3 4

Quelque chose comme

1 7 2 5 9 6

nécessite 4 transpositions (7, 2), (7, 6), (6,5), (9, 7)

Mise à jour (9/7/11): question modifiée pour utiliser la "transposition" au lieu de "swaps" pour faire référence aux échanges non adjacents.

ds.algorithms co.combinatorics sorting sova
la source

Et si vous pouviez simplement échanger des voisins? comment puis-je déterminer le nombre minimum de swaps?

Réponses:

Si vous ne traitez qu'avec des permutations de éléments, alors vous aurez besoin exactement de swaps, où est le nombre de cycles dans la décomposition en cycle disjoint de . Comme cette distance est bi-invariante, la transformation de en (ou en , ou inversement) nécessite tels mouvements. $n$ $n-c(\pi)$ $c(\pi)$ $\pi$ $\pi$ $\sigma$ $A$ $B$ $n-c(\sigma^{-1}\circ\pi)$

Anthony Labarre
la source

Bien qu'il ait voté pour cela il y a longtemps, il a juste cliqué aujourd'hui. Comme un Rubik's cube, non: D?

sova

La distance de permutation peut également être intégrée isométriquement dans l'espace euclidien. Pour chaque chaîne s, construisez une matrice où si se produit avant et vaut zéro sinon. Alors la distance de Frobenius est la distance d'échange . (à partir des diapositives de Graham Cormode ). Pas aussi élégant que la réponse d'Anthony, mais assez facile à calculer. $M(s)$ $M_{ij} = 1$ $i$ $j$ $\|M(s) - M(s')\|^2$ $d(s,s')$

Mise à jour: veuillez consulter les commentaires d'Oleksandr

Suresh Venkat
la source

Il me semble que dans la présentation de Graham, ils signifient la norme spectrale ( ) et non la norme Frobenius ( ).

‖ A ‖_{2}

$\|A\|_2$

‖ A ‖_{F}

$\|A\|_F$

Oleksandr Bondarenko

même si tout ce que vous voulez faire est de compter les différences, alors le carré de la norme frobenius devrait fonctionner correctement?

Suresh Venkat

qui est bien sûr la distance de Hamming pour les matrices 0-1

Suresh Venkat

Vous avez raison sur l'égalité entre le carré de la norme de Frobenius et la distance de Hamming. Je voudrais ajouter que la distance de Hamming divisée par est égale à la distance d'échange. Mais la question portait sur la distance de transposition ("Un swap est défini comme la commutation de la position de 2 éléments dans la liste") et non sur la distance de swap. Ce qui concerne la norme spectrale c'est son carré égal à la distance de swap.

2

$2$

Oleksandr Bondarenko

Oleksandr: Donc je suppose que vous interprétez le "swapping" comme "l'échange de deux éléments adjacents"?

Anthony Labarre