¿Podemos ordenar sin permutaciones?

12

Es bien sabido que la clasificación de permutaciones por transposición está en , ya que el número mínimo de transposiciones requeridas para clasificar π S n es exactamente i n v ( π ) = { ( i , j ) [ n ] × [ n ] : i < j  y  π ( i ) > π ( j ) }PπSninv(π)={(i,j)[n]×[n]:i<j and π(i)>π(j)}. Esta noción de "número de inversión" también tiene aplicaciones en la combinatoria algebraica, por ejemplo, permite dotar a de una estructura reticular, llamada permutoedro y basada en el orden débil de Bruhat.Sn

Puede ser esclarecedor reformular el problema en términos de teoría de grupos. Se nos da un grupo con el grupo electrógeno Γ y un mapeo i G : Γ G , y otro grupo H en el que G actúa de forma transitiva, y queremos resolver el siguiente problema: dado h H , encontrar una longitud mínima w Γ tal que i G ( w ) . h = 1 H . En el caso de permutación, G = H =GΓiG:ΓGHGhHwΓiG(w).h=1H y Γ es el conjunto de transposiciones.G=H=SnΓ

Pregunta: ¿hay otras instancias de este problema que admitan algoritmos eficientes?

NisaiVloot
fuente
Bueno, el problema es probablemente fácil cuando G=iZri
mobius dumpling

Respuestas:

6

XH(x1,,xn)Xnx1xn=1XGBnσiBnH

σi(x1,,xn)=(x1,,xi1,xi+1,xi+11xixi+1,,xn).

σiii+1

NisaiVloot
fuente
4

G=H=SnG=H=An

G=H=SnΓw

Yoshio Okamoto
fuente