Symmetric group conjugacy class iterator

[videlec]

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.

CC: @amritanshu-prasad

Component: combinatorics

Keywords: symmetric group, permutations, iterator

Author: Travis Scrimshaw, Vincent Delecroix

Branch/Commit: 9f7e86a

Reviewer: Amritanshu Prasad

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

[tscrim]

Commit: e32c6d0

[tscrim]

Branch: public/groups/conjugacy_classes_symmetric_group-16018

[tscrim]

comment:3

I iterate over partitions l of n and construct a permutation representative by

(1,2, ... l₁) (l₁+1, ... l₁+l₂) ... (l₁+...+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:

fcbf99d	Added direct conjugacy classes methods.
8774bf7	Added an iterator method for conjugacy classes.
e32c6d0	Fixed doc typo in representatives.

[tscrim]

Changed author from Vincent Delecroix to Travis Scrimshaw

[videlec]

comment:4

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

[tscrim]

comment:5

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?

[videlec]

comment:6

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 and Permutations_n

What do you think?

Vincent

[sagetrac-git]

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

996c06d

Add code for iteration over a conjugacy class

[sagetrac-git]

Changed commit from e32c6d0 to 996c06d

[sagetrac-git]

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

1339080

Created a class for conjugacy classes for the symmetric group.

[sagetrac-git]

Changed commit from 996c06d to 1339080

[tscrim]

comment:9

Replying to @videlec:

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

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. 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

[sagetrac-git]

Changed commit from 1339080 to f77593d

[amritanshu-prasad]

comment:11

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

[tscrim]

Changed author from Travis Scrimshaw to Travis Scrimshaw, Vincent Delecroix

[tscrim]

Reviewer: Amritanshu Prasad

[tscrim]

comment:12

Thanks Amri. You're change is good with me.

[vbraun]

comment:13

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
**********************************************************************

[sagetrac-git]

Changed commit from f77593d to 9f7e86a

[sagetrac-git]

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

9f7e86a

Trivial doctest fixes.

[tscrim]

comment:16

Trivial fixes.

[vbraun]

Changed branch from public/groups/conjugacy_classes_symmetric_group-16018 to 9f7e86a