# $2+2+\dots+2$ cycle conjugation classes of the symmetric group $S_n$

Command GroupElements[SymmetricGroup[4]] gives me all cycles of all conjugation classes. But I'm only interested in the 2+2 class ($$2+2$$ being one of the integer partitions of $$n=4$$ corresponding to the cycle of size 3 in this case). I could filter out all three cycles from the result but for the partition $$\underbrace{2+2+\dots+2}_{n/2}$$ it is impractical and slow for a bigger $$n$$ since it lists all $$2^n$$ cycles -- the size of the class I'm after is 'only' $$(n-1)!!$$. How to generate them directly and fast (at least for moderate $$n\approx20$$)?

You can use the function partitions from Rojo's answer to Partition a set into subsets of size $$k$$:

partitions[list_, l_] := Join @@
Table[
{x, ##} & @@@ partitions[list ~Complement~ x, l],
{x, Subsets[list, {l}, Binomial[Length[list] - 1, l - 1]]}
]

partitions[list_, l_] /; Length[list] === l := {{list}}


For example:

partitions[Range[4], 2]


{{{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2, 3}}}

and

partitions[Range[10], 2] //Length
9!!


945

945

His function will work reasonable fast up to about $$n=16$$. If you need to go to $$n=20$$, you might want to figure out how to speed it up.

A slight speedup can be obtained by using memoization:

partitions2[list_, l_] := partitions2[list, l] = Join @@
Table[
{x, ##} & @@@ partitions2[list ~Complement~ x, l],
{x, Subsets[list, {l}, Binomial[Length[list] - 1, l - 1]]}
]

partitions2[list_, l_] /; Length[list] === l := {{list}}


A speed comparison:

r1 = partitions[Range[16], 2];//AbsoluteTiming
r2 = partitions2[Range[16], 2]; //AbsoluteTiming

r1 === r2


{26.1082, Null}

{4.3307, Null}

True

Still, since 18 produces 34459425 partitions and 20 produces 654729075 partitions, you probably will need to come up with a version that produces only a subset of the total.

• Great, that is what I need, thanks Jun 16, 2019 at 22:06
• That macro is complicated for me to be able to speed it up. Could somebody help? Jun 16, 2019 at 22:20