ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 17 Feb 2015 17:21:08 -0600Iterator for conjugacy classes of Snhttp://ask.sagemath.org/question/7794/iterator-for-conjugacy-classes-of-sn/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,
VincentTue, 07 Dec 2010 09:48:05 -0600http://ask.sagemath.org/question/7794/iterator-for-conjugacy-classes-of-sn/Comment by benjaminfjones for <p>Hello,</p>
<p>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.</p>
<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!).</p>
<ul>
<li>Do there exist algorithms for iteration through conjugacy classes of the symmetric group which is as close as possible as a Gray code ?</li>
<li>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.</li>
<li>Is there something yet implemented in softwares included in Sage ?</li>
</ul>
<p>Thanks,
Vincent</p>
http://ask.sagemath.org/question/7794/iterator-for-conjugacy-classes-of-sn/?comment=19344#post-id-19344I 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.Wed, 25 Jul 2012 05:44:15 -0500http://ask.sagemath.org/question/7794/iterator-for-conjugacy-classes-of-sn/?comment=19344#post-id-19344Answer by vdelecroix for <p>Hello,</p>
<p>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.</p>
<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!).</p>
<ul>
<li>Do there exist algorithms for iteration through conjugacy classes of the symmetric group which is as close as possible as a Gray code ?</li>
<li>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.</li>
<li>Is there something yet implemented in softwares included in Sage ?</li>
</ul>
<p>Thanks,
Vincent</p>
http://ask.sagemath.org/question/7794/iterator-for-conjugacy-classes-of-sn/?answer=25863#post-id-25863Hello 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)]Tue, 17 Feb 2015 17:21:08 -0600http://ask.sagemath.org/question/7794/iterator-for-conjugacy-classes-of-sn/?answer=25863#post-id-25863