Opened 7 years ago
Closed 6 years ago
#16018 closed enhancement (fixed)
Symmetric group conjugacy class iterator
Reported by:  vdelecroix  Owned by:  Vincent Delecroix 

Priority:  major  Milestone:  sage6.5 
Component:  combinatorics  Keywords:  symmetric group, permutations, iterator 
Cc:  amri  Merged in:  
Authors:  Travis Scrimshaw, Vincent Delecroix  Reviewers:  Amritanshu Prasad 
Report Upstream:  N/A  Work issues:  
Branch:  9f7e86a (Commits)  Commit:  9f7e86adf3143ac51a26b44aa3e128f53260aeca 
Dependencies:  Stopgaps: 
Description
Using the underlying GAP commands it takes forever to iterate over conjugacy classes of the Symmetric group. In this ticket we implement a very simple and very naive one that does the job.
Change History (17)
comment:1 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:2 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:3 Changed 6 years ago by
 Branch set to public/groups/conjugacy_classes_symmetric_group16018
 Cc amri added
 Commit set to e32c6d00a732658dc27be760a4ae83f446ae0b76
 Status changed from new to needs_review
comment:4 Changed 6 years ago by
Hi Travis,
The title of the ticket was perhaps not clear enough, I wanted to iterate through the elements of a given conjugacy class... Let us assume that the purpose changed ;)
Vincent
comment:5 followup: ↓ 6 Changed 6 years ago by
Ah, so the description should have been something like:
Using the underlying GAP commands it takes forever to iterate over a conjugacy class of the Symmetric group. In this ticket we implement a very simple and very naive one that does the job.
I'd definitely like to speed that up as well. Do you have that code to iterate over a particular conjugacy class? I'm happy to add that onto here and review it.
A question, do you think should we add similar methods to Permutations_n
?
comment:6 in reply to: ↑ 5 ; followup: ↓ 9 Changed 6 years ago by
Replying to tscrim:
Ah, so the description should have been something like:
Using the underlying GAP commands it takes forever to iterate over a conjugacy class of the Symmetric group. In this ticket we implement a very simple and very naive one that does the job.
I'd definitely like to speed that up as well. Do you have that code to iterate over a particular conjugacy class? I'm happy to add that onto here and review it.
I do. Let me add it to the branch.
A question, do you think should we add similar methods to
Permutations_n
?
I don't know. Most of the time I found that playing with classes makes life harder and I mostly program using tuple and/or lists (this is what my iterator is). One way to make it would be:
 have this iterator (somehow hidden) that output lists
 use it for both
SymmetricGroup
andPermutations_n
What do you think?
Vincent
comment:7 Changed 6 years ago by
 Commit changed from e32c6d00a732658dc27be760a4ae83f446ae0b76 to 996c06d0e24f0f68dee83476518ca0dafb7e286f
Branch pushed to git repo; I updated commit sha1. New commits:
996c06d  Add code for iteration over a conjugacy class

comment:8 Changed 6 years ago by
 Commit changed from 996c06d0e24f0f68dee83476518ca0dafb7e286f to 1339080a3d55bd3116947ff49210b5deb9a053cd
Branch pushed to git repo; I updated commit sha1. New commits:
1339080  Created a class for conjugacy classes for the symmetric group.

comment:9 in reply to: ↑ 6 Changed 6 years ago by
Replying to vdelecroix:
I do. Let me add it to the branch.
Thanks.
A question, do you think should we add similar methods to
Permutations_n
?I don't know. Most of the time I found that playing with classes makes life harder and I mostly program using tuple and/or lists (this is what my iterator is). One way to make it would be:
 have this iterator (somehow hidden) that output lists
 use it for both
SymmetricGroup
andPermutations_n
What do you think?
Well, I went ahead and played with classes. I implemented a class specifically for conjugacy classes of the symmetric group (in part for the future with implementing a direct computation of character tables directly in Sage, in part to override the behavior of ConjugacyClassGap
and allow easier future refactoring). However I left your function as a lowlevel iterator.
I'm leaning towards just leaving it until we consider Partitions_n
as a group (at which time we'll be throwing a lot of functionality at it I think). I designed the current version with this in mind (that I didn't want to do this right now :p
).
comment:10 Changed 6 years ago by
 Commit changed from 1339080a3d55bd3116947ff49210b5deb9a053cd to f77593d31d42a4d09bc14d23ce3e1713404c07e8
comment:11 Changed 6 years ago by
Looks good to me. I tested it out for some examples and it seemed to work correctly. There seemed to be one small issue in the documentation for index_set() which I corrected.
New commits:
8a519d8  Merge branch 'public/groups/conjugacy_classes_symmetric_group16018' of git://trac.sagemath.org/sage into conjugacy_classes_symmetric_group16018

f77593d  minor correction in documentation

comment:12 Changed 6 years ago by
 Milestone changed from sage6.4 to sage6.5
 Reviewers set to Amritanshu Prasad
 Status changed from needs_review to positive_review
Thanks Amri. You're change is good with me.
comment:13 Changed 6 years ago by
Doctests fail:
sage t long warnlong 38.5 src/sage/groups/perm_gps/permgroup.py ********************************************************************** File "src/sage/groups/perm_gps/permgroup.py", line 1855, in sage.groups.perm_gps.permgroup.PermutationGroup_generic.conjugacy_class Failed example: G.conjugacy_class(g) Expected: Conjugacy class of (1,2,3,4) in Symmetric group of order 4! as a permutation group Got: Conjugacy class of cycle type [4] in Symmetric group of order 4! as a permutation group ********************************************************************** 1 item had failures: 1 of 4 in sage.groups.perm_gps.permgroup.PermutationGroup_generic.conjugacy_class [787 tests, 1 failure, 8.76 s]  sage t long warnlong 38.5 src/sage/groups/perm_gps/permgroup.py # 1 doctest failed  Total time for all tests: 8.9 seconds cpu time: 5.1 seconds cumulative wall time: 8.8 seconds sage t long warnlong 38.5 src/sage/groups/conjugacy_classes.py ********************************************************************** File "src/sage/groups/conjugacy_classes.py", line 27, in sage.groups.conjugacy_classes Failed example: G.conjugacy_class(g) Expected: Conjugacy class of (1,2,3,4) in Symmetric group of order 4! as a permutation group Got: Conjugacy class of cycle type [4] in Symmetric group of order 4! as a permutation group **********************************************************************
comment:14 Changed 6 years ago by
 Status changed from positive_review to needs_work
comment:15 Changed 6 years ago by
 Commit changed from f77593d31d42a4d09bc14d23ce3e1713404c07e8 to 9f7e86adf3143ac51a26b44aa3e128f53260aeca
Branch pushed to git repo; I updated commit sha1. New commits:
9f7e86a  Trivial doctest fixes.

comment:17 Changed 6 years ago by
 Branch changed from public/groups/conjugacy_classes_symmetric_group16018 to 9f7e86adf3143ac51a26b44aa3e128f53260aeca
 Resolution set to fixed
 Status changed from positive_review to closed
I iterate over partitions
l
ofn
and construct a permutation representative by(1,2, ... l_{1}) (l_{1}+1, ... l_{1}+l_{2}) ... (l_{1}+...+l_{k1}, .. n)
where
k
is the length ofl
. Here's my timings:Without my branch:
So we get about 14x20x speedup in the representative function, but surprisingly, minimal gain in listing all conjugacy classes. Anyways, I think this is an improvement. I've also added a specific iterator method for the conjugacy classes.
New commits:
Added direct conjugacy classes methods.
Added an iterator method for conjugacy classes.
Fixed doc typo in representatives.