TCS-TR-A-12-56Date: Sun Apr 22 00:19:44 2012 Title: A PiDD-Based Method for Generating Conjugacy Classes of Permutation Groups Authors: Norihiro Yamada and Shin-ichi Minato Contact:
Abstract. Conjugacy classes are important notions in group theory and computational group theory, since in our method for example, computing conjugacy classes of the symmetric group $S_n$ of degree $n \in N^+$ enables us to partition a set of permutations according to cycle types; also, they are essential in computing the character table of a group. In this paper, we present the method to compute the conjugacy classes of a permutation group by utilizing $\pi$DDs, the efficient data structure for manipulating sets of permutations. The advantages of using $\pi$DDs are that they achieve the compact representation of sets of permutations, which is suitable for retaining all class elements, while previous methods have had difficulty in storing all class elements of a vast permutation group because of storage limitations; also they provide convenient operations such as membership test and computing unions or intersections. These strong points propose useful applications; for example, $\pi$DDs provide an algorithm to partition a set of permutations according to cycle types, as stated above. our algorithm offers an efficient way to compute the number of nonequivalent colorings in the presence of symmetries, which is a problem in the field of combinatorics.\fi The experimental results for $S_n$ ($n \leqslant 12$) demonstrate the efficiency of $\pi$DDs. Thus, we have shown that $\pi$DDs are excellent for computing conjugacy classes of some permutation groups, and suggested effective applications, which have been difficult for previous methods. ©Copyright 2012 Authors |