Revision history [back]

Hello,

I would like to iterate through elements of a conjugacy classe of the symmetric group. In other words, I'm looking for an algorithm which given a partition p = [p1,...,pk] provides an iterator over permutations with cycle decomposition with lengths given by p. There is one way which uses GAP, but as I have to iterate through conjugacy classes of S(12) it is infinitely slow inside Sage. On the other hand, there is a very efficient way to iteratate through all permutations : there exists a "Gray code" for which two consecutive permutations differ by a swap. 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 permutations of given length (the number k above) ?
• Is there something yet implemented in softwares included in Sage ?

Thanks, Vincent

Hello,

I would like to iterate through elements of a conjugacy classe classes of the symmetric group. group Sn. In other words, I'm looking for an algorithm which given a an integer partition p = [p1,...,pk] of n provides an iterator over permutations with cycle decomposition with lengths whose length of cycles is exactly given by 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. Sage. On the other hand, there is a very useful efficient way to iteratate iterate through all permutations of Sn : there exists a "Gray code" for which two consecutive permutations differ by a swap. swap (ie exchange of images between two elements). Such a method is implemented in cython in sage.combinat.permutation_cython (thanks Tom Boothby).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 permutations 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