Podemos classificar sem permutações?

É sabido que a classificação de permutações por transposição está em , pois o número mínimo de transposições necessárias para classificar é exatamente . Essa noção de "número de inversão" também tem aplicações na combinatória algébrica, por exemplo, permite dotar uma estrutura de treliça, chamada permutoedro e baseada na fraca ordem de Bruhat. π ∈ S n i n v ( π ) = { ( i , j ) ∈ [ n ] × [ n ] : i < j  e  π ( 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$

Pode ser esclarecedor reformular o problema em termos da teoria dos grupos. Recebemos um grupo com o grupo gerador e um mapeamento , e outro grupo no qual age transitivamente, e queremos resolver o seguinte problema: dado , encontre um comprimento mínimo tal que . No caso de permutação, e é o conjunto de transposições.Γ i L : Γ * → L 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$

Pergunta: existem outras instâncias deste problema que admitem algoritmos eficientes?

Não tenho uma resposta definitiva para sua pergunta, mas a "trança de tranças" parece um possível candidato. De acordo com esta entrada da Wikipedia , podemos defini-la da seguinte forma. Seja um grupo e represente o conjunto de tuplas modo que . Se deixarmos ser o grupo de tranças gerado pelos movimentos , podemos definir uma ação de sobre por:H ( x 1 , … , x n ) ∈ X n x 1 … x n = 1 X G B n σ i B n$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).$

Ou seja, combina o efeito de um swap e uma conjugação de posições e . Pode ser possível resolver esse problema de maneira otimizada em tempo polinomial, o que responderia à sua pergunta. i i + $\sigma_i$$i$$i+1$

O artigo a seguir de Mark Jerrum estudou o problema que você mencionou quando e G = H = A n (o grupo alternado):$G=H=S_n$$G=H=A_n$

• Mark Jerrum: A complexidade de encontrar seqüências de geradores de comprimento mínimo. Theor. Comput. Sci. 36: 265-289 (1985) http://dx.doi.org/10.1016/0304-3975(85)90047-7 .

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