Conjugacy classes -- how to generate them for a list to be sorted? 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?

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.
