Here is a function that might belong somewhere in the
distribution (with the appropriate name). It is translated
from matlab code. It benefits greatly from compiling. I
tried using arrays and mode_declare, etc., but I don't
understand how to use them really, and I didn't find any
improvement in speed, over simply compiling. For the test
given below, this is about 10 times faster than the function
in Combinatorica in Mathematica 8 (but maybe there is some
way to compile the Mma function as well.)
(%i1) m : listify(permutations(makelist(i,i,8)))$
Half the permutations are odd and half are even.
(%i2) apply("+",map(SignaturePermutation,m));
(%o2) 0
-- John Lapeyre
/* Compute the signature of a permutation. Eg.
SignaturePermutation([1,2,3]) -> 1
SignaturePermutation([2,1,3]) -> -1
translated from matlab code by Derek O'Connor 20 March 2011
" If ce(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 sgn(p)=(?1)ce(n).
Here is an O(n) Matlab function that computes the sign of a
permutation p by traversing each cycle of p and (implicitly)
counting the number of even-length cycles."
*/
SignaturePermutation(p):=block([n:length(p),k,visited,knext,L,sgn:1],
visited:makelist(false,n),
for k thru n do
if not visited[k]
then (knext:k,L:0,
while not visited[knext] do
(L:1+L,visited[knext]:true,
knext:p[knext]),
if evenp(L) then sgn:-sgn),sgn)