ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 07 Dec 2010 09:48:05 -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,
VincentvdelecroixTue, 07 Dec 2010 09:48:05 -0600http://ask.sagemath.org/question/7794/