Können wir ohne Permutationen sortieren?

Es ist bekannt, dass das Sortieren von Permutationen durch Transposition in , da die minimale Anzahl von Transpositionen, die zum Sortieren von erforderlich sind, genau . Dieser Begriff der "Inversionszahl" hat auch Anwendungen in der algebraischen Kombinatorik, zum Beispiel erlaubt er, mit einer Gitterstruktur zu versehen, die Permutoheder genannt wird und auf der schwachen Bruhat-Ordnung basiert. π ∈ S n i n v ( π ) = { ( i , j ) ∈ [ n ] × [ n ] : i < j  und  π ( i ) > π ( j ) } S $\sf{P}$$\pi \in S_n$$inv(\pi) = \{ (i,j) \in [n] \times [n] : i < j \text{ and } \pi(i) > \pi(j) \}$$S_n$

Es kann aufschlussreich sein, das Problem gruppentheoretisch neu zu fassen. Wir erhalten eine Gruppe mit dem Generatorsatz und einem Mapping , und eine andere Gruppe auf die transitiv einwirkt, und wir wollen das folgende Problem lösen: gegeben , find eine minimale Länge so dass . Im Permutationsfall ist und die Menge der Transpositionen.Γ i G : Γ * → G H G h ∈ H w ∈ Γ * i G ( w ) . h = 1 H G = H = S n$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$

Frage: Gibt es andere Fälle dieses Problems, die effiziente Algorithmen zulassen?

Ich habe keine definitive Antwort auf Ihre Frage, aber "Braid Sorting" scheint ein möglicher Kandidat zu sein. Entsprechend diesem Wikipedia-Eintrag können wir ihn wie folgt definieren. Sei eine Gruppe, und sei die Menge der Tupel so dass . Wenn wir die durch die Bewegungen erzeugte Zopfgruppe , können wir eine Aktion von über definieren, wir :$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).$

Das heißt, kombiniert den Effekt eines Swaps und einer Konjugation an den Positionen und . Es könnte möglich sein, dieses Problem in der Polynomzeit optimal zu lösen, was Ihre Frage beantworten würde.$\sigma_i$$i$$i+1$

$G=H=S_n$$G=H=A_n$

• Mark Jerrum: Die Komplexität des Findens von Generatorsequenzen mit minimaler Länge. Theor. Comput. Sci. 36: 265-289 (1985) http://dx.doi.org/10.1016/0304-3975(85)90047-7 .

$G=H=S_n$$\Gamma$$w$