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: | sage-6.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 sage-6.2 to sage-6.3
comment:2 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:3 Changed 6 years ago by
- Branch set to public/groups/conjugacy_classes_symmetric_group-16018
- 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 follow-up: ↓ 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 ; follow-up: ↓ 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 low-level 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_group-16018' of git://trac.sagemath.org/sage into conjugacy_classes_symmetric_group-16018
|
f77593d | minor correction in documentation
|
comment:12 Changed 6 years ago by
- Milestone changed from sage-6.4 to sage-6.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 --warn-long 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 --warn-long 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 --warn-long 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_group-16018 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, ... l1) (l1+1, ... l1+l2) ... (l1+...+lk-1, .. n)
where
k
is the length ofl
. Here's my timings:Without my branch:
So we get about 14x-20x 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.