How does one compute the sign of a permutation?

Solution 1:

So you have a permutation $f: X \to X$ for which you can efficiently compute $f(x)$ from $x$.

I think a good way to do any of the things you mentioned is to make a checklist for the elements of $X$. Then you can start with the first unchecked element and follow the chain $x, f(x), f(f(x))$, etc. checking off each element as you find it until you reach an element that is already checked. You have now traversed one cycle. Then you can pick the next unchecked element and traverse that cycle, and so on until all elements are checked.

While you traverse a cycle you can easily

1. Count the cycle length
2. Record the cycle, or
3. Record transpositions

All this works in roughly linear time. Obviously just counting the cycle lengths is going to be the fastest.

Solution 2:

It's worth mentioning the quadratic time algorithm, since it can be faster for small permutations:

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

I.e., the sign is negative iff there are an odd number of misordered pairs of indices. This algorithm also works if we're interested in the permutation defined by an unsorted list of integers where the cycle structure can't be determined in linear time.

Solution 3:

If $c_e(n)$ is the number of even-length cycles in a permutation $p$ of length $n$, then one of the formulas for the sign of a permutation $p$ is $\text{sgn}(p) = (-1)^{c_e(n)}$.

Here is an $O(n)$ Matlab function that computes the sign of a permutation vector $p(1:n)$ by traversing each cycle of $p$ and (implicitly) counting the number of even-length cycles. The number of cycles in a random permutation of length $n$ is $O(H_n)$, where $H_n$ is the $n$-th Harmonic Number.

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 

Solution 4:

The inverse permutation can be constructed as a sequence of $n-1$ transpositions via Gaussian Elimination with partial pivoting, $P A = L U$, where $A$ is the original permutation matrix, $P=A^{-1}$, and $L=U=I$. Since the signature of the inverse permutation is the same as that of the original permutation, this procedure yields the sign of the permutation.

Thankfully, this algorithm can be run in linear time by maintaining the permutation and its inverse throughout a short-circuited Gaussian Elimination procedure since it can easily be seen that the Schur complement updates will always be zero.