The sign of a permutation $\sigma\in \mathfrak{S}_n$, written ${\rm sgn}(\sigma)$, is defined to be +1 if the permutation is even and -1 if it is odd, and is given by the formula
$${\rm sgn}(\sigma) = (-1)^m$$
where $m$ is the number of transpositions in the permutation when written as a product of transpositions.
Alternatively the sign is -1 if, when we express $\sigma$ as a product of disjoint cycles, the result contains an odd number of even-length cycles. Otherwise the sign is +1.
My permutations are expressed as tuples $(\sigma_1,\dots,\sigma_n)$, so neither the expression of the tuple as a product of disjoint cycles nor as a product of transpositions are immediately available to me.
This suggests two high-algorithms to compute the sign of a permutation:
-
Express the permutation as a product of transpositions and count the number of transpositions.
-
Express the permutation as a product of disjoint cycles and count the number of even-length cycles.
What are typical algorithms for accomplishing these tasks, and how do they vary in running type depending on $n$? Are there more efficient algorithms for calculating the sign of a permutation?
Additional info
The motivation is to quickly decide whether instances of the fifteen puzzle are solvable. I want to generate a large number of solvable instances of the fifteen puzzle for testing some search algorithms. At the moment I generate a random instance, and test whether it is solvable by trying to solve it with depth-first search, which is fairly slow going, and won't generalize well to larger puzzles (24 puzzle, 35 puzzle…) due to time and memory limitations. Since solvable instances of the fifteen puzzle are in 1-1 correspondence with even elements of $\mathfrak{S}_{16}$, I figure that there must be a faster way of generating solvable instances.
It has just occurred to me that a better way of generating solvable instances of the puzzle might be to generate an even number of transpositions and multiply them together to generate an even permutation. I'd prefer an algorithm that was guaranteed to return an even distribution over $\mathfrak{S}_n$ though, and in fact I'm now sufficiently interested in the answer to this question in its own right.
Best Answer
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
All this works in roughly linear time. Obviously just counting the cycle lengths is going to be the fastest.