Some improvements for signed permutations
Closed this issue · 25 comments
Signed permutations should not be harder to use than permutations.
In particular, this ticket adds the possibility to create a signed permutation by calling SignedPermutation(l), adds a __getitem__ and __call__ method, cycle decomposition, and multiplicative order.
Component: combinatorics
Author: Martin Rubey
Branch/Commit: 0a22ca9
Reviewer: Travis Scrimshaw
Issue created by migration from https://trac.sagemath.org/ticket/33328
Description changed:
---
+++
@@ -1 +1,3 @@
+Signed permutations should not be harder to use than permutations.
+In particular, this ticket adds the possibility to create a signed permutation by calling `SignedPermutation(l)`, adds a `__getitem__` method, cycle decomposition and multiplicative order.
Author: Martin Rubey
I need help to add the correct __classcall_private__, I never get that right.
Incidentally, Permutation doesn't have order either, PermutationGroupElement does. I don't see a good reason for that, though.
Branch pushed to git repo; I updated commit sha1. New commits:
aa63825 | allow easy creation of signed permutations |
It is a big unfair to call these fixes because they are not bugs. However, thank you for these improvements.
I think the __getitem__ could be made more efficient by directly accessing the underlying information:
def __getitem__(self, i):
return (self._perm[i], self._colors[i])
A similar change should be done for SignedPermutations as the iteration has a different behavior (which is natural and by design even though it is a behavior change when going to the subclass). I think we should try and optimize this method a bit.
Please also add a doctest for to_cycles(singletons=False, use_min=False).
Can you switch to Python variable lower_case_var_anmes?
It would be good to not call the variable next to not conflict with the iterator advancement function.
I am wondering if it might be better to use the underlying permutions to_cycle() and then add in the computation based on the “colors”. This might not necessarily be faster, but it would reduce some of the code duplication. Although it would obfuscate the code a bit. Your thoughts on this? One advantage of this implementation is that it could easily be modified for general colored permutations, where the order() could then be lifted.
Branch pushed to git repo; I updated commit sha1. New commits:
935a623 | add len, improve getitem, slightly polish code |
I am all for reusing to_cycles, but cannot do this right now, possibly tonight.
That's the simplest I could come up with, and it looks like a great waste. Any ideas?
def to_cycles(pi):
cycles = pi.permutation().to_cycles()
result = []
for c in cycles:
s = 1
nc = [c[0]]
for i in range(1, len(c)):
s = pi._colors[c[i - 1] - 1] * s
nc.append(s * c[i])
s = pi._colors[c[-1] - 1] * s
if s < 0:
nc.extend([-e for e in nc])
result.append(tuple(nc))
return result
Thank you for looking into it. That is basically what I had in mind, although you could just convert each cycle to a list and modify the elements of that list. Upon seeing it, I agree that it is a bit computationally wasteful. It might be worth profiling to see how much slower this version is in comparison.
Another option might be to refactor out with the permutation code and see how much speed we lose there by generalizing it (in that case, there would be a lot of multiplication by 1).
I will look into this today.
Changed branch from u/mantepse/some_fixes_for_signed_permutations to public/combinat/signed_perm_improvements-33328
Description changed:
---
+++
@@ -1,3 +1,3 @@
Signed permutations should not be harder to use than permutations.
-In particular, this ticket adds the possibility to create a signed permutation by calling `SignedPermutation(l)`, adds a `__getitem__` method, cycle decomposition and multiplicative order.
+In particular, this ticket adds the possibility to create a signed permutation by calling `SignedPermutation(l)`, adds a `__getitem__` and {{{__call__}} method, cycle decomposition, and multiplicative order.
Reviewer: Travis Scrimshaw
I decided to just go with the current method with some slight modifications. It could be refactored, but I figure the extra overhead to make it work for permutations is not worth it.
I added also a __call__ for signed permutations.
Here is a comparison with your comment:9 code (slightly tweaked to optimize it):
sage: pi = SignedPermutation([-4, 5, -1, 2, -3])
sage: pi.to_cycles2()
[(-1, -4, -2, 5, 3, 1, 4, 2, -5, -3)]
sage: %timeit pi.to_cycles()
7.58 µs ± 51.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
sage: %timeit pi.to_cycles2() # comment:9 code
9.53 µs ± 65.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
versus my pushed code:
sage: %timeit pi.to_cycles() # pushed commit
7.55 µs ± 109 ns per loop per loop (mean ± std. dev. of 7 runs, 100000 loops each)
Comparison of my commit:
sage: pi = SignedPermutations(7)([2,-1,4,-6,-5,-3,7])
sage: %timeit pi.to_cycles()
10.9 µs ± 303 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
sage: %timeit pi.to_cycles(singletons=False)
11.2 µs ± 223 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
versus your version:
sage: %timeit pi.to_cycles()
12.4 µs ± 3.27 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
sage: %timeit pi.to_cycles(singletons=False)
13.5 µs ± 3.96 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
With the branch I pushed, slices are faster for colored and signed permutations:
sage: C = ColoredPermutations(4, 3)
sage: s1,s2,t = C.gens()
sage: x = s1*s2*t
sage: %timeit x[:]
1.19 µs ± 2.14 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
pi = SignedPermutation([-4, 5, -1, 2, -3])
sage: %timeit pi[:]
1.31 µs ± 18.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
sage: %timeit pi[1::2]
1.42 µs ± 15.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
versus before
2.23 µs ± 30.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
6.07 µs ± 40.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
3.62 µs ± 22.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
New commits:
7310387 | Merge branch 'u/mantepse/some_fixes_for_signed_permutations' of git://trac.sagemath.org/sage into public/combinat/signed_perm_improvements-33328 |
0a22ca9 | Added __call__() and improvements to to_cycles() and __getitem__() to SignedPermutation. |
Perfect! Thank you in particular for adding __call__!
I am all for it!
Green bot too. :)
Description changed:
---
+++
@@ -1,3 +1,3 @@
Signed permutations should not be harder to use than permutations.
-In particular, this ticket adds the possibility to create a signed permutation by calling `SignedPermutation(l)`, adds a `__getitem__` and {{{__call__}} method, cycle decomposition, and multiplicative order.
+In particular, this ticket adds the possibility to create a signed permutation by calling `SignedPermutation(l)`, adds a `__getitem__` and `__call__` method, cycle decomposition, and multiplicative order.
I am also happy with the rest of your changes, so if you are okay with mine, then go ahead an set a positive review.
Thank you for checking my changes and the working to improve Sage!
Changed branch from public/combinat/signed_perm_improvements-33328 to 0a22ca9