¿Cómo se calcula el signo de una permutación?

Question

El signo de una permutación $\sigma\in \mathfrak{S}_n$ , escrito ${\rm sgn}(\sigma)$ se define como +1 si la permutación es par y -1 si es impar, y viene dada por la fórmula

$${\rm sgn}(\sigma) = (-1)^m$$

donde $m$ es el número de transposiciones en la permutación cuando se escribe como un producto de transposiciones.

Alternativamente el signo es -1 si, cuando expresamos $\sigma$ como producto de ciclos disjuntos, el resultado contiene un número impar de ciclos de longitud par. En caso contrario, el signo es +1.

Mis permutaciones se expresan como tuplas $(\sigma_1,\dots,\sigma_n)$ por lo que ni la expresión de la tupla como producto de ciclos disjuntos ni como producto de transposiciones están inmediatamente disponibles para mí.

Esto sugiere dos algoritmos elevados para calcular el signo de una permutación:

1. Expresa la permutación como un producto de transposiciones y cuenta el número de transposiciones.

2. Expresa la permutación como un producto de ciclos disjuntos y cuenta el número de ciclos pares.

¿Cuáles son los algoritmos típicos para llevar a cabo estas tareas, y cómo varían en el tipo de ejecución dependiendo de $n$ ? ¿Existen algoritmos más eficaces para calcular el signo de una permutación?

---

Información adicional

La motivación es decidir rápidamente si las instancias del quince rompecabezas son solucionables. Quiero generar un gran número de instancias resolubles de los quince rompecabezas para probar algunos algoritmos de búsqueda. Por el momento genero una instancia aleatoria, y pruebo si es solucionable intentando resolverla con la búsqueda de profundidad primero, lo cual es bastante lento, y no se generaliza bien a rompecabezas más grandes (rompecabezas de 24, rompecabezas de 35...) debido a las limitaciones de tiempo y memoria. Dado que las instancias resolubles del rompecabezas quince están en correspondencia 1-1 con elementos pares de $\mathfrak{S}_{16}$ Me imagino que debe haber una forma más rápida de generar instancias resolubles.

Se me acaba de ocurrir que una forma mejor de generar instancias resolubles del puzzle podría ser generar un número par de transposiciones y multiplicarlas para generar una permutación par. Preferiría un algoritmo que garantizara una distribución par sobre $\mathfrak{S}_n$ Sin embargo, y de hecho ahora estoy lo suficientemente interesado en la respuesta a esta pregunta por derecho propio.

Answer 1

Así que tienes una permutación $f: X \to X$ para el que se puede calcular eficazmente $f(x)$ de $x$ .

Creo que una buena manera de hacer cualquiera de las cosas que has mencionado es hacer una lista de control de los elementos de $X$ . Entonces puede empezar con el primer elemento no marcado y seguir la cadena $x, f(x), f(f(x))$ etc. marcando cada elemento a medida que lo encuentra hasta llegar a un elemento que ya esté marcado. Ya has recorrido un ciclo. A continuación, puede elegir el siguiente elemento no comprobado y recorrer ese ciclo, y así hasta que todos los elementos estén marcados.

Mientras atraviesas un ciclo puedes fácilmente

1. Contar la duración del ciclo
2. Registrar el ciclo, o
3. Registrar las transposiciones

Todo esto funciona en un tiempo aproximadamente lineal. Obviamente, sólo contando las longitudes de los ciclos va a ser lo más rápido.

Answer 2

Vale la pena mencionar el algoritmo de tiempo cuadrático, ya que puede ser más rápido para permutaciones pequeñas:

$$\textrm{sgn}(\sigma) = (-1)^{\sum_{0 \le i<j<n} (\sigma_i>\sigma_j)}$$

Es decir, el signo es negativo si hay un número impar de pares de índices mal ordenados. Este algoritmo también funciona si nos interesa la permutación definida por una lista no ordenada de enteros en la que la estructura del ciclo no se puede determinar en tiempo lineal.

Answer 3

Si $c_e(n)$ es el número de ciclos de longitud par en una permutación $p$ de longitud $n$ entonces una de las fórmulas para el signo de una permutación $p$ es $\text{sgn}(p) = (-1)^{c_e(n)}$ .

Aquí hay un $O(n)$ Función de Matlab que calcula el signo de un vector de permutación $p(1:n)$ atravesando cada ciclo de $p$ y (implícitamente) contando el número de ciclos de longitud par. El número de ciclos en una permutación aleatoria de longitud $n$ es $O(H_n)$ , donde $H_n$ es el $n$ -en Número de armónicos .

function sgn = SignPerm(p);
% ----------------------------------------------------------
% Calculates the sign of a permutation p.
% p is a row vector p(1,n), which represents the permutation.
% sgn(p) = (-1)^(No. of even-length cycles)
% Complexity : O(n + ncyc) ~ O(n + Hn) ~~ O(n+log(n)) steps.
%
% Derek O'Connor 20 March 2011.
% ----------------------------------------------------------
n   = length(p);
visited(1:n) = false;                  % Logical vector which marks all p(k)
                                       % not visited.
sgn = 1;
for k = 1:n
    if ~visited(k)                     % k not visited, start of new cycle
        next = k;
        L = 0;
        while ~visited(next)           % Traverse the current cycle k
            L = L+1;                   % and find its length L
            visited(next) =  true;
            next    = p(next);
        end
        if rem(L,2) == 0               % If L is even, change sign.
            sgn = -sgn;
        end
    end % if ~visited(k)
end % for k

Answer 4

La permutación inversa puede construirse como una secuencia de $n-1$ transposiciones mediante la eliminación gaussiana con pivotaje parcial, $P A = L U$ , donde $A$ es la matriz de permutación original, $P=A^{-1}$ y $L=U=I$ . Dado que la firma de la permutación inversa es la misma que la de la permutación original, este procedimiento arroja el signo de la permutación.

Afortunadamente, este algoritmo puede ejecutarse en tiempo lineal manteniendo la permutación y su inversa a lo largo de un procedimiento de eliminación gaussiana en cortocircuito, ya que se puede ver fácilmente que las actualizaciones del complemento de Schur siempre serán cero.

Answer 5

$sgn(\sigma)=\prod_{i<j}\frac{\sigma(i)-\sigma(j)}{i-j}$ es cuadrático, pero sencillo de codificar.