Looks useful, but I don't think it's linear, more like O(n^2). After all,
accessing the *n*th element of a Maxima list is O(n).
For example, on my machine, SignaturePermutation(makelist(i,i,1,1000))
takes 0.23 sec, while SignaturePermutation(makelist(i,i,1,10000)); takes
19.8 sec. (uncompiled) Compiled numbers are 0.05 / 6.42.
-s
On my machine,
On Wed, Dec 28, 2011 at 11:18, John Lapeyre <lapeyre.math122a at gmail.com>wrote:
>
> 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)
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>