#16018: Symmetric group conjugacy class iterator
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner: Vincent Delecroix
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: symmetric group, | Merged in:
permutations, iterator | Reviewers:
Authors: Travis Scrimshaw | Work issues:
Report Upstream: N/A | Commit:
Branch: | e32c6d00a732658dc27be760a4ae83f446ae0b76
public/groups/conjugacy_classes_symmetric_group-16018| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Travis Scrimshaw', 'oldvalue': u'Vincent
Delecroix'}):
* status: new => needs_review
* commit: => e32c6d00a732658dc27be760a4ae83f446ae0b76
* cc: amri (added)
* branch: => public/groups/conjugacy_classes_symmetric_group-16018
* author: Vincent Delecroix => Travis Scrimshaw
Comment:
I iterate over partitions `l` of `n` and construct a permutation
representative by
(1,2, ... l,,1,,) (l,,1,,+1, ... l,,1,,+l,,2,,) ... (l,,1,,+...+l,,k-1,,,
.. n)
where `k` is the length of `l`. Here's my timings:
{{{
sage: S = SymmetricGroup(5)
sage: %timeit S.conjugacy_classes_representatives()
100 loops, best of 3: 2.08 ms per loop
sage: S = SymmetricGroup(12)
sage: %timeit S.conjugacy_classes_representatives()
10 loops, best of 3: 29.5 ms per loop
sage: S = SymmetricGroup(25)
sage: %timeit S.conjugacy_classes_representatives()
1 loops, best of 3: 1.06 s per loop
sage: S = SymmetricGroup(5)
sage: %timeit S.conjugacy_classes()
10 loops, best of 3: 99.3 ms per loop
sage: S = SymmetricGroup(12)
sage: %timeit S.conjugacy_classes()
1 loops, best of 3: 1.1 s per loop
}}}
Without my branch:
{{{
sage: S = SymmetricGroup(5)
sage: %timeit S.conjugacy_classes_representatives()
1 loops, best of 3: 55.8 ms per loop
sage: S = SymmetricGroup(12)
sage: %timeit S.conjugacy_classes_representatives()
1 loops, best of 3: 565 ms per loop
sage: S = SymmetricGroup(25)
sage: %timeit S.conjugacy_classes_representatives()
1 loops, best of 3: 14.5 s per loop
sage: S = SymmetricGroup(5)
sage: %timeit S.conjugacy_classes()
10 loops, best of 3: 115 ms per loop
sage: S = SymmetricGroup(12)
sage: %timeit S.conjugacy_classes()
1 loops, best of 3: 1.23 s per loop
}}}
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:
||[http://git.sagemath.org/sage.git/commit/?id=fcbf99d07d98d86e78d12ac513c9c478201e419b
fcbf99d]||{{{Added direct conjugacy classes methods.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=8774bf728ad6495091a92885066950ebfa9af7fb
8774bf7]||{{{Added an iterator method for conjugacy classes.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=e32c6d00a732658dc27be760a4ae83f446ae0b76
e32c6d0]||{{{Fixed doc typo in representatives.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/16018#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
