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 vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:2 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:3 Changed 6 years ago by tscrim

  • Authors changed from Vincent Delecroix to Travis Scrimshaw
  • Branch set to public/groups/conjugacy_classes_symmetric_group-16018
  • Cc amri added
  • Commit set to e32c6d00a732658dc27be760a4ae83f446ae0b76
  • Status changed from new to needs_review

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

(1,2, ... l1) (l1+1, ... l1+l2) ... (l1+...+lk-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:

fcbf99dAdded direct conjugacy classes methods.
8774bf7Added an iterator method for conjugacy classes.
e32c6d0Fixed doc typo in representatives.

comment:4 Changed 6 years ago by vdelecroix

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: Changed 6 years ago by 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.

A question, do you think should we add similar methods to Permutations_n?

comment:6 in reply to: ↑ 5 ; follow-up: Changed 6 years ago by vdelecroix

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

comment:7 Changed 6 years ago by git

  • Commit changed from e32c6d00a732658dc27be760a4ae83f446ae0b76 to 996c06d0e24f0f68dee83476518ca0dafb7e286f

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

996c06dAdd code for iteration over a conjugacy class

comment:8 Changed 6 years ago by git

  • Commit changed from 996c06d0e24f0f68dee83476518ca0dafb7e286f to 1339080a3d55bd3116947ff49210b5deb9a053cd

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

1339080Created a class for conjugacy classes for the symmetric group.

comment:9 in reply to: ↑ 6 Changed 6 years ago by tscrim

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

comment:10 Changed 6 years ago by git

  • Commit changed from 1339080a3d55bd3116947ff49210b5deb9a053cd to f77593d31d42a4d09bc14d23ce3e1713404c07e8

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

8a519d8Merge branch 'public/groups/conjugacy_classes_symmetric_group-16018' of git://trac.sagemath.org/sage into conjugacy_classes_symmetric_group-16018
f77593dminor correction in documentation

comment:11 Changed 6 years ago by amri

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:

8a519d8Merge branch 'public/groups/conjugacy_classes_symmetric_group-16018' of git://trac.sagemath.org/sage into conjugacy_classes_symmetric_group-16018
f77593dminor correction in documentation

comment:12 Changed 6 years ago by tscrim

  • Authors changed from Travis Scrimshaw to Travis Scrimshaw, Vincent Delecroix
  • 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 vbraun

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 vbraun

  • Status changed from positive_review to needs_work

comment:15 Changed 6 years ago by git

  • Commit changed from f77593d31d42a4d09bc14d23ce3e1713404c07e8 to 9f7e86adf3143ac51a26b44aa3e128f53260aeca

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

9f7e86aTrivial doctest fixes.

comment:16 Changed 6 years ago by tscrim

  • Status changed from needs_work to positive_review

Trivial fixes.

comment:17 Changed 6 years ago by vbraun

  • Branch changed from public/groups/conjugacy_classes_symmetric_group-16018 to 9f7e86adf3143ac51a26b44aa3e128f53260aeca
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.