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

Luego de investigar con especialistas en el tema, programadores de diversas ramas y maestros hemos dado con la solución a la interrogande y la plasmamos en este post.

Solución:

Así que tienes una permutación $f: X to X$ para la cual puedes calcular eficientemente $f(x)$ a partir de $x$.

Creo que una buena manera de hacer cualquiera de las cosas que mencionaste es hacer una lista de verificación para los elementos de $X$. Luego puede comenzar con el primer elemento sin marcar y seguir la cadena $x, f(x), f(f(x))$, etc. marcando cada elemento a medida que lo encuentre hasta llegar a un elemento que ya está marcado. Ahora has atravesado un ciclo. Luego, puede elegir el siguiente elemento no marcado y atravesar ese ciclo, y así sucesivamente hasta que todos los elementos estén marcados.

Mientras atraviesa un ciclo, puede fácilmente

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

Todo esto funciona en un tiempo aproximadamente lineal. Obviamente, solo contar la duración del ciclo será lo más rápido.

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

$$textrmsgn(sigma) = (-1)^sum_0 le isigma_j)$$

Es decir, el signo es negativo si y sólo si hay un número impar de pares de índices desordenados. Este algoritmo también funciona si estamos interesados ​​en la permutación definida por una lista desordenada de enteros donde la estructura del ciclo no se puede determinar en tiempo lineal.

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 $textsgn(p ) = (-1)^c_e(n)$.

Aquí hay una función de Matlab $O(n)$ que calcula el signo de un vector de permutación $p(1:n)$ recorriendo 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$-ésimo Número armónico.

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 

Más adelante puedes encontrar las interpretaciones de otros sys admins, tú incluso tienes la habilidad insertar el tuyo si te gusta.

---

---

Utiliza Nuestro Buscador