Peut-on trier sans permutations?

12

Il est bien connu que le tri des permutations par transposition est dans , car le nombre minimum de transpositions nécessaires pour trier est exactement . Cette notion de "nombre d'inversion" trouve également des applications en combinatoire algébrique, par exemple elle permet de doter d'une structure de réseau, appelée permutoèdre et basée sur l'ordre de Bruhat faible. $\sf{P}$ $\pi \in S_n$ $inv(\pi) = \{ (i,j) \in [n] \times [n] : i < j \text{ and } \pi(i) > \pi(j) \}$ $S_n$

Il peut être éclairant de reformuler le problème en termes de théorie des groupes. On nous donne un groupe avec un groupe électrogène et un mappage , et un autre groupe sur lequel agit de manière transitoire, et nous voulons résoudre le problème suivant: étant donné , trouver une longueur minimale telle que . Dans le cas de la permutation, et est l'ensemble des transpositions. $G$ $\Gamma$ $i_G : \Gamma^* \rightarrow G$ $H$ $G$ $h \in H$ $w \in \Gamma^*$ $i_G(w).h = 1_H$ $G = H = S_n$ $\Gamma$

Question: existe-t-il d'autres instances de ce problème qui admettent des algorithmes efficaces?

sorting NisaiVloot
la source

Eh bien, le problème est probablement facile lorsque

G = \prod_{i} Z_{r_{i}}

$G=\prod_i Z_{r_i}$

mobius dumpling

6

Je n'ai pas de réponse définitive à votre question, mais le "tri des tresses" semble un candidat possible. Selon cette entrée de wikipedia, nous pouvons le définir comme suit. Soit un groupe et désigne l'ensemble de tuples tels que . Si on laisse le groupe de tresses généré par les mouvements , on peut définir une action de sur par: $X$ $H$ $(x_1,\ldots,x_n) \in X^n$ $x_1 \ldots x_n = 1_X$ $G$ $B_n$ $\sigma_i$ $B_n$ $H$

$\sigma_i(x_1,\ldots,x_n) = (x_1,\ldots,x_{i-1},x_{i+1},x_{i+1}^{-1} x_i x_{i+1},\ldots,x_n).$

C'est-à-dire que combine l'effet d'un swap et d'une conjugaison aux positions et . Il pourrait être possible de résoudre ce problème de manière optimale en temps polynomial, ce qui répondrait à votre question. $\sigma_i$ $i$ $i+1$

NisaiVloot
la source

4

L'article suivant de Mark Jerrum a étudié le problème que vous avez mentionné lorsque et (le groupe alterné): $G=H=S_n$ $G=H=A_n$

Mark Jerrum: La complexité de la recherche de séquences de générateur de longueur minimale. Théor. Comput. Sci. 36: 265-289 (1985) http://dx.doi.org/10.1016/0304-3975(85)90047-7 .

Entre autres résultats, il a prouvé que lorsque et est l'ensemble des «transpositions cycliquement adjacentes», la longueur minimale de ces peut être trouvée en temps polynomial. $G=H=S_n$ $\Gamma$ $w$

Yoshio Okamoto
la source

Peut-on trier sans permutations?

Réponses: