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 ) }. 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.
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 = y Γ es el conjunto de transposiciones.
Pregunta: ¿hay otras instancias de este problema que admitan algoritmos eficientes?
Respuestas:
fuente
fuente