Ask Your Question
6

Iterator for conjugacy classes of Sn

asked 2010-12-07 09:48:05 -0500

updated 2012-07-20 22:58:21 -0500

Hello,

I would like to iterate through elements of a conjugacy classes of the symmetric group Sn. In other words, I'm looking for an algorithm which given an integer partition p = [p1,...,pk] of n provides an iterator over permutations with cycle decomposition whose length of cycles is exactly given by p.

There is one way which uses GAP, but as I have to iterate through conjugacy classes of S(12) and it is infinitely slow inside Sage. On the other hand, there is a useful efficient way to iterate through all permutations of Sn : there exists a "Gray code" for which two consecutive permutations differ by a swap (ie exchange of images between two elements). Such a method is implemented in cython in sage.combinat.permutation_cython (thanks Tom Boothby!).

  • Do there exist algorithms for iteration through conjugacy classes of the symmetric group which is as close as possible as a Gray code ?
  • Does there exist a better algorithm if we consider partitions of given length (the number k above) ? In other words, not iterating through conjugacy classes but through permutations with fixed number of cycles in their cycle decomposition.
  • Is there something yet implemented in softwares included in Sage ?

Thanks, Vincent

edit retag flag offensive close merge delete

Comments

1

I don't know of any such algorithm that is included in Sage. It sounds like you may know enough to implement something like this. The problem with iterating over conjugacy classes in S_{12} is that GAP must produce the full list of classes before returning control to Sage. This is what takes forever. As far as I know there isn't a "generator" type implementation for this in GAP or Sage.

benjaminfjones gravatar imagebenjaminfjones ( 2012-07-25 05:44:15 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
2

answered 2015-02-17 17:21:08 -0500

Hello Vincent,

This is now available in sage-6.5

sage: from sage.groups.perm_gps.symgp_conjugacy_class import conjugacy_class_iterator
sage: for p in conjugacy_class_iterator([2,2,2]):
....:     print p
[(1, 2), (3, 4), (5, 6)]
[(1, 2), (3, 5), (4, 6)]
[(1, 2), (3, 6), (4, 5)]
[(1, 3), (2, 4), (5, 6)]
[(1, 3), (2, 5), (4, 6)]
[(1, 3), (2, 6), (4, 5)]
[(1, 4), (2, 3), (5, 6)]
[(1, 4), (2, 5), (3, 6)]
[(1, 4), (2, 6), (3, 5)]
[(1, 5), (2, 3), (4, 6)]
[(1, 5), (2, 4), (3, 6)]
[(1, 5), (2, 6), (3, 4)]
[(1, 6), (2, 3), (4, 5)]
[(1, 6), (2, 4), (3, 5)]
[(1, 6), (2, 5), (3, 4)]
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2010-12-07 09:48:05 -0500

Seen: 388 times

Last updated: Feb 17 '15