Conjugacy classes -- how to generate them for a list to be sorted?

Question

In another thread I had brought up the notion of sorting a list of four randomly scrambled items.

It was mentioned that they can be broken down into 5 conjugacy classes: (), (12), (123), (12)(34) and (1234)

Can anyone explain how these work or if there is a general way to list all possible conjugacies? For instance, what about a list of size 6?

Answer 1

The conjugacy classes of the symmetric group $S_n$ correspond to the partitions of $n$. How to generate all partitions of $n$ is described e.g. in The Art of Computer Programming by Donald E. Knuth; see Algorithm P on p. 2 of this online version.

Answer 2

I write this answer only to make sure that OP realises the connection between the problem stated and the formulation. I think this however could be closed as exact duplicate.

---

The notion of sorting $n$ items you're talking about is formally called the permutations of $n$ symbols. The notion of conjugacy discussed in the answer corresponds to the action of group on itself by conjugation.

---

Well, you are asking for the number of conjugacy classes in a symmetric group of order $n$. Yes, there is a nice description.

I'll recall the main result while I'll let you go through the details in an exactly same answer $^\dagger$ I had written over here.

Main result:

The number of conjugacy classes in $S_n$ equals the number of partitions of $n$.

---

We'll give a way to list an exhaustive set or representatives for the conjugacy classes.

Write down all the additive partitions of $n$. To each partition, associate a representative as follows.

For each number appearing in the partition, attach with it a disjoint cycle of that length. The product of all such cycles represents a unique conjugacy class. It is best illustrated by an example for $4$:

$$\begin{align*}Id &\cong 1+1+1+1\\(1234)&\cong 4\\(12)(34) &\cong 2+2\\ (34) &\cong 1+1+2(\text{since (1) and (2) are omitted in this notation})\\(123)&\cong 3+1\end{align*}$$

---

$\dagger$ This answer of mine deals with exactly this question.

Answer 3

I'm just going to add on to what Kanna wrote. In the answer he links he proves that permutations of the same cycle type are all conjugate (and indeed that cycle type is necessarily invariant under conjugation, so that the conjugacy classes are precisely the cycle types). Ultimately this puts classes in bijection with integer partitions. Explicitly, we may list representatives via

$$(a_1,a_2,\dots,a_k)\vdash n \quad \longleftrightarrow \quad (\underbrace{1\;2\;3\;\cdots}_{a_1})(\underbrace{\cdots\cdots}_{a_2})\cdots (\underbrace{\cdots n-1\; n}_{a_k})$$

For example, the integer partition $(3,2,2,1)\vdash8$ corresponds to the permutation $(123)(45)(67)(8)$.