On Feb 13, 11:41 pm, Florent Hivert <[email protected]> wrote: > 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: >
OK. I should have looked at the member functions of a permutation... > 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, but you need to return the parity (1 if even, else -1) of the number of cycles of even length. Is it the way the member function is implemented? > > 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
