search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.46k stars 482 forks source link

Add signed permutations #16010

Open 01f5781a-be80-4f39-b75f-3542e9378080 opened 10 years ago

01f5781a-be80-4f39-b75f-3542e9378080 commented 10 years ago

Add support for signed permutations to Sage.

Statistics:

Other things that should be easy:

Things that might take some time to do the 'right' way:

CC: @kevindilks @mantepse @stumpc5

Component: combinatorics

Branch/Commit: u/csar/ticket/16010 @ cf623c1

Issue created by migration from https://trac.sagemath.org/ticket/16010

01f5781a-be80-4f39-b75f-3542e9378080 commented 10 years ago

Branch: u/csar/ticket/16010

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Commit: 248e197

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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
01f5781a-be80-4f39-b75f-3542e9378080 commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,15 +1,15 @@
 Add support for signed permutations to Sage.

 Statistics:
-- Which entries are less than zero
-- Number of entries less than zero
-- Location of descents (keeping in mind there's a 'descent at zero' for signed permutations if the first entry is negative)
-- Number of descents
+- 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
 - Number of Inversions

 Other things that should be easy:
-- 'Absolute value map' (ie, remove all signs).
+- 'Absolute value map' (ie, remove all signs). (done)
 - Reverse/complement
 - Longest Element
 - To_matrix (make it compatible with the existing Weyl group stuff?)
tscrim commented 10 years ago
comment:5

Some other things that would be nice:

I can also do (some of) the reviewing when this is ready too.

01f5781a-be80-4f39-b75f-3542e9378080 commented 10 years ago
comment:6

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.

tscrim commented 10 years ago
comment:7

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}).

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

198ec1fAdd maj, fdes, fmaj, length, inv
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 248e197 to 198ec1f

01f5781a-be80-4f39-b75f-3542e9378080 commented 10 years ago

Description changed:

--- 
+++ 
@@ -5,8 +5,9 @@
 - 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
-- Number of Inversions
+- 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)
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

3ac8edbFixed the parent/element/category mess. Hopefully
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 198ec1f to 3ac8edb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 3ac8edb to cf623c1

tscrim commented 9 years ago
comment:13

See also #17411.

01f5781a-be80-4f39-b75f-3542e9378080 commented 9 years ago
comment:14

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.)

tscrim commented 9 years ago
comment:15

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).

stumpc5 commented 7 years ago
comment:16

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?

tscrim commented 7 years ago
comment:18

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.

stumpc5 commented 7 years ago
comment:19

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

tscrim commented 7 years ago
comment:20

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.

1adc0eef-8957-46d9-975b-2dd71dfbd9ba commented 7 years ago
comment:21

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

01f5781a-be80-4f39-b75f-3542e9378080 commented 7 years ago
comment:22

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.