How can I compute whether a sequence is an even or odd permutation of an increasing sequence? [closed]

Question

Variants of this question have been crossposted to Stack Overflow and Mathematics Stack Exchange. Additional answers may be found at these other sites.

Computational Science People:

I originally posed this as part of a question at https://math.stackexchange.com/questions/379809/is-there-a-name-for-this-function-parity-of-a-finite-sequence . The title pretty much says it all. Given a finite sequence of real numbers which I know are distinct, I want an easy way to compute whether it is an even permutation of an increasing sequence or an odd permutation of an increasing sequence. For example, $(5, 1.3, 8, 6, 10.5)$ is an even permutation of the increasing sequence $(1.3, 5, 6, 8, 10)$, so the answer is "even". $(2, 3, 5, 1)$ is an odd permutation of the increasing sequence $(1, 2, 3, 5)$, so the answer is "odd". I can get Matlab to give me a permutation vector, which for my first example would be $[2\ 1\ 4\ 3\ 5]$, but I cannot find a built-in function in Matlab to compute the sign of that permutation vector. If I could get Matlab to give me the permutation matrix, I could take the determinant of that matrix. People have posted quite long Matlab files on the Web to accomplish this, but I'm hoping I can avoid that. I would also be willing to use Maple.

Please no nitpicking or unconstructive comments, which are very common at Math Stack Exchange. I have less experience here, but I'm hoping people are more polite here.

Stefan (STack Exchange FAN)

Answer 1

Suppose you have a permutation vector permVec. Then a permutation matrix should be calculated as follows (modulo some MATLAB syntax bugs, since it's been a while):

permMat = function permVecToMat(permVec)
    n = length(permVec);
    permMat = zeros(n,n);
    for i = 1:n
        permMat(i, permVec(i)) = 1
    end
end

Then you just take the determinant, and you're done. Consider the code BSD-licensed, even though the Stack Exchange license is CC-BY-SA 3.0 (and I loathe it).

An alternate way of calculating the sign of a permutation would be to convert it into a product of transpositions. If the number of transpositions in such a decomposition is even, the permutation is even; otherwise, the permutation is odd. However, I don't know an algorithm for decomposing a permutation into a product of transpositions.