自然数の分割の列挙アルゴリズム

$n$の分割を列挙したくなったとき，どうやるんだったか毎回忘れるので，自分用に書いておく．

自然数の単調非増加な有限列で，和が$n$であるものを$n$の分割という．
例えば，$(3,3,3,1)$は長さ$4$の$10$の分割である．
長さ$k$の$n$の分割の集合を$P(n,k)$とかく．

本稿では$P(n,k)$の元を列挙するアルゴリズムを与える．
なおこのアルゴリズムは，$\bigcup _{k=1}^{n}P(n,k)$とすることで$n$の全ての分割を列挙するためにも使うことができる．

記法の定義

自然数の列$\lambda =({\lambda }_1,\dots ,{\lambda }_r)$に対して
$$\begin{array}{rl}\lambda +\mathbf{1}& \triangleq ({\lambda }_1+1,\dots {\lambda }_r+1),\\ \lambda 1& \triangleq ({\lambda }_1,\dots ,{\lambda }_r,1)\end{array}$$
と定義する．
また，$1^n\triangleq (1,1,\dots ,1)$（$1$を$n$個並べたもの）と定義する．

アルゴリズムのもととなる数学的性質

疑似コード

procedure $P(n,k)$
if $n=k$ then return $\{1^n\}$ end if;
if $n\le 0$ or $n<k$ then return $\mathrm{\varnothing }$ end if;
$S$←$P(n-1,k-1)$;
$T$←$P(n-k,k)$;
return $(\bigcup _{\lambda \in S}\{\lambda 1\})\cup (\bigcup _{\lambda \in T}\{\lambda +\mathbf{1}\})$
end procedure