Hi There, > This might be not so efficient, as it would involve a call to GAP, > etc... > One can instead just count (mod 2) the number of swaps the bubble sort > does to > sort your permutation in increasing order > > def sig(p): > a = list(p) > ctr = 1 > la = len(a) - 1 > while True: > done = True > i = 0 > while i < la: > if a[i]>a[i+1]: > a[i+1],a[i] = a[i],a[i+1] > ctr = -ctr > done = False > break > i += 1 > if done: > return ctr > > sage: sig([4, 3, 5, 1, 2]) > -1 > > PS. needless to say, rewriting this in Cython would speed things up > even more.
Two remark: 1) It is also already implemented in permutation.py: sage: Permutation([1,4,2,3]).signature() 1 sage: Permutation([1,4,3,2]).signature() -1 2) if you want to play with large permutations, there is a much better algorithm, namely, decompose the permutations into cycles an return n-#cycles if the permutations belongs to SG_n. Indeed bubble sort is quadratic wheras decomposing to cycle is linear. Cheers, Florent -- To post to this group, send an email to [email protected] To unsubscribe from this group, send an email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
