Conjugate Partition

Author

Eric W. Weisstein
September 8, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/ConjugatePartition.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/ConjugatePartition.html.

©2021 Wolfram Research, Inc. except for portions noted otherwise

Figure

p2=ResourceFunction["ConjugatePartition"][p1={6,3,3,2,1}]

ResourceFunction["ConjugatePartition"][p2]==p1

ResourceFunction["FerrersDiagram"][#]&/@{p1,p2}

Algorithms

FunctionRepository

ConjugatePartition0[l_]:=ResourceFunction["ConjugatePartition"][l]

ConjugatePartition0[{6,3,3,2,1}]

Position

Eric's version from either ca. 1999:

ConjugatePartition[l_]:=Module[{i,r=Reverse[l],n=Length[l]},Table[n+1-Position[r,_?(#≥i&),Infinity,1][[1,1]],{i,l[[1]]}]]

Implementation from Function Repo:
https://resources.wolframcloud.com/FunctionRepository/resources/ConjugatePartition

NestWhileList

Version from Arnoud B. from Sep 7 2021, which is faster and simpler:

ConjugatePartition2[e_]:=Length/@Most[
NestWhileList[
Function[{s},
Select[s-1,#>0&]
],
e,
#=!={}&]]

Compiled

A compiled version, slightly more complicated because Select can return an empty list which the compiler does not like:

ConjugatePartition3=FunctionCompile[
Function[{Typed[e,TypeSpecifier["PackedArray"]["MachineInteger", 1]]},
Module[{ee=e,more,Typed[res,"DynamicArray"]=CreateDataStructure["DynamicArray"]},
more=Length[ee]>0;
While[more,
res["Append",Length[ee]];
If[
First[ee-1]>0,
ee=Select[ee-1,#>0&],
more=False
];
];
Normal[res]
]]]

Sanity check:

ConjugatePartition3[{4,3,2,1,1}]

Timing comparisons

Performance comparisons:

ip=IntegerPartitions[40];

AbsoluteTiming[one=ConjugatePartition/@ip;]

AbsoluteTiming[two=ConjugatePartition2/@ip;]

AbsoluteTiming[three=ConjugatePartition3/@ip;]

one===two===three