Opened 7 years ago
Last modified 3 years ago
#16010 new enhancement
Add signed permutations
Reported by:  csar  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  combinatorics  Keywords:  
Cc:  kdilks, mantepse, stumpc5  Merged in:  
Authors:  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/csar/ticket/16010 (Commits)  Commit:  cf623c139bbdf4d9eab053d133b894c46ed95d83 
Dependencies:  Stopgaps: 
Description (last modified by )
Add support for signed permutations to Sage.
Statistics:
 Which entries are less than zero (done)
 Number of entries less than zero (done)
 Location of descents (keeping in mind there's a 'descent at zero' for signed permutations if the first entry is negative) (done)
 Number of descents (done)
 fdes and fmaj (done)
 Number of Inversions (done)
Most of these don't have proper docstrings yet.
Other things that should be easy:
 'Absolute value map' (ie, remove all signs). (done)
 Reverse/complement
 Longest Element
 To_matrix (make it compatible with the existing Weyl group stuff?)
Things that might take some time to do the 'right' way:
 Pattern Avoidance
 Bruhat Order
 Signed RSK
Change History (22)
comment:1 Changed 7 years ago by
 Branch set to u/csar/ticket/16010
 Created changed from 03/25/14 14:31:38 to 03/25/14 14:31:38
 Modified changed from 03/25/14 14:31:38 to 03/25/14 14:31:38
comment:2 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:3 Changed 7 years ago by
 Commit set to 248e197720f429cc0b6c4470da3762260b060a36
comment:4 Changed 7 years ago by
 Description modified (diff)
comment:5 Changed 7 years ago by
Some other things that would be nice:
 Make this into a permutation group (similar to
SymmetricGroup
).  Add methods to transform elements into a
SymmetricGroup
elements via the natural "diagram folding".  Implement the even signed permutation group.
 Implement the natural coercions between the above.
I can also do (some of) the reviewing when this is ready too.
comment:6 Changed 7 years ago by
I'm debating whether it makes sense to split the permutation group aspect off as a separate ticket that depends on this one. I don't suppose it really matters, aside from perhaps making the housekeeping and reviewing easier. I guess I need to think about how Permutations
and SymmetricGroup
connect first.
comment:7 Changed 7 years ago by
Since this is the first implementation, it would actually make things harder to review IMO. In some ways Permutations
and SymmetricGroup
have duplication, but there is a good argument for having Permutations
to be separate since we don't necessarily want to consider "standard" permutations (i.e. the base set {1, ..., n}
).
comment:8 Changed 6 years ago by
 Commit changed from 248e197720f429cc0b6c4470da3762260b060a36 to 198ec1f60c5760594e2e87cc725f0131fc7c9529
Branch pushed to git repo; I updated commit sha1. New commits:
198ec1f  Add maj, fdes, fmaj, length, inv

comment:9 Changed 6 years ago by
 Description modified (diff)
comment:10 Changed 6 years ago by
 Commit changed from 198ec1f60c5760594e2e87cc725f0131fc7c9529 to 3ac8edbc075f4c8771833525175db0317fbecb97
Branch pushed to git repo; I updated commit sha1. New commits:
3ac8edb  Fixed the parent/element/category mess. Hopefully

comment:11 Changed 6 years ago by
 Commit changed from 3ac8edbc075f4c8771833525175db0317fbecb97 to cf623c139bbdf4d9eab053d133b894c46ed95d83
Branch pushed to git repo; I updated commit sha1. New commits:
b625b66  Add docstring and fix length/sign mixup

eaf942e  Add permutation statistics for the two choices of order.

8129479  Add signed permutation option

68c3427  Add metaclass, start working on cycles

b3c4751  Finish to_cycles and cycle_string

cf623c1  Add ability to create signed permutations from cycles

comment:12 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:13 followup: ↓ 14 Changed 6 years ago by
See also #17411.
comment:14 in reply to: ↑ 13 Changed 5 years ago by
comment:15 Changed 5 years ago by
I would first start by running some timings to see which implementation does better (for signed permutations). (There might be certain situations where one beats the other too.) It might also be worthwhile moving some of the statistics over to #17411 if they work in greater generality.
However before you do timings, it would be a good idea to make sure everything is on equal footing. In particular, the first input to any Element
subclass should be a parent object. This is the standard way to create element classes in Sage (this also means you don't have to "recreate" the parent object for every new element; while this is not much overhead, it does give some).
comment:16 Changed 3 years ago by
I wanted to check what the current status here is? I would like to add signed permutations to FindStat and this implementation seems to provide everything I need for that... Is there any plan to finalize this any time soon?
comment:17 Changed 3 years ago by
 Cc mantepse stumpc5 added
comment:18 Changed 3 years ago by
At this point, we have signed (and colored) permutations in Sage from #17411. However, I have not compared them to this implementation for efficiency. In the direction of combining the code here, we could add the statistics and come back to an efficiency comparison afterwards.
comment:19 Changed 3 years ago by
What about the element constructor, I didn't find SignedPermutation([2,1,3])
comment:20 Changed 3 years ago by
That one is a bit more debatable whether we want that or not. Of course, you can do this:
sage: SP = SignedPermutations(3) sage: SP([2,1,3]) [2, 1, 3] sage: SP([2,1,3])^2 [1, 2, 3]
However, it is in line with everything else we do for similar things, so I don't have any real objections.
comment:21 Changed 3 years ago by
I can try and look at this some, but won't have access to a "real" computer until around July 4th.
comment:22 Changed 3 years ago by
Basically, this seemed to be superseded by #17411 and I wasn't sure what to do about it, so it's languished. I totally missed the notification for comment 15, so never did the work suggested there. I'm happy to go back and work on some of that.
Branch pushed to git repo; I updated commit sha1. New commits:
Complete merge
Add abs to SignedPermutation; probably doesn't work
Import permutation, add descent and negative entry statistics
Fixed lazy_attribute import