2
$\begingroup$

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$)?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

Addendum

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.