Opened 6 years ago

Last modified 2 years ago

#16010 new enhancement

Add signed permutations

Reported by: csar Owned by:
Priority: major Milestone: sage-6.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 csar)

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 6 years ago by csar

  • 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 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:3 Changed 6 years ago by git

  • Commit set to 248e197720f429cc0b6c4470da3762260b060a36

Branch pushed to git repo; I updated commit sha1. New commits:

38864fbComplete merge
850a786Add abs to SignedPermutation; probably doesn't work
d7642e9Import permutation, add descent and negative entry statistics
248e197Fixed lazy_attribute import

comment:4 Changed 6 years ago by csar

  • Description modified (diff)

comment:5 Changed 6 years ago by tscrim

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 6 years ago by csar

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 6 years ago by tscrim

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 git

  • Commit changed from 248e197720f429cc0b6c4470da3762260b060a36 to 198ec1f60c5760594e2e87cc725f0131fc7c9529

Branch pushed to git repo; I updated commit sha1. New commits:

198ec1fAdd maj, fdes, fmaj, length, inv

comment:9 Changed 6 years ago by csar

  • Description modified (diff)

comment:10 Changed 5 years ago by git

  • Commit changed from 198ec1f60c5760594e2e87cc725f0131fc7c9529 to 3ac8edbc075f4c8771833525175db0317fbecb97

Branch pushed to git repo; I updated commit sha1. New commits:

3ac8edbFixed the parent/element/category mess. Hopefully

comment:11 Changed 5 years ago by git

  • Commit changed from 3ac8edbc075f4c8771833525175db0317fbecb97 to cf623c139bbdf4d9eab053d133b894c46ed95d83

Branch pushed to git repo; I updated commit sha1. New commits:

b625b66Add docstring and fix length/sign mixup
eaf942eAdd permutation statistics for the two choices of order.
8129479Add signed permutation option
68c3427Add metaclass, start working on cycles
b3c4751Finish to_cycles and cycle_string
cf623c1Add ability to create signed permutations from cycles

comment:12 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:13 follow-up: Changed 5 years ago by tscrim

See also #17411.

comment:14 in reply to: ↑ 13 Changed 4 years ago by csar

Replying to tscrim:

See also #17411.

I'm finally in a position to work on this again. Should I work off what you have in #17411 to add the stuff here that doesn't overlap? (Looks like that's mostly the permutation statistics.)

comment:15 Changed 4 years ago by tscrim

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 2 years ago by stumpc5

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?

Last edited 2 years ago by stumpc5 (previous) (diff)

comment:17 Changed 2 years ago by stumpc5

  • Cc mantepse stumpc5 added

comment:18 Changed 2 years ago by tscrim

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 2 years ago by stumpc5

What about the element constructor, I didn't find SignedPermutation([2,-1,3])

comment:20 Changed 2 years ago by tscrim

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 2 years ago by kdilks

I can try and look at this some, but won't have access to a "real" computer until around July 4th.

comment:22 Changed 2 years ago by csar

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.

Note: See TracTickets for help on using tickets.