自然数の分割の列挙アルゴリズム
$n$の分割を列挙したくなったとき，どうやるんだったか毎回忘れるので，自分用に書いておく．
自然数の単調非増加な有限列で，和が$n$であるものを$n$の分割という．
例えば，$(3,3,3,1)$は長さ$4$の$10$の分割である．
長さ$k$の$n$の分割の集合を$P(n,k)$とかく．
本稿では$P(n,k)$の元を列挙するアルゴリズムを与える．
なおこのアルゴリズムは，$\bigcup_{k=1}^nP(n,k)$とすることで$n$の全ての分割を列挙するためにも使うことができる．
記法の定義
自然数の列$\lambda=(\lambda_1,\ldots,\lambda_r)$に対して
\begin{align}
\lambda+{\bf 1}&\triangleq(\lambda_1+1,\ldots\lambda_r+1),\\
\lambda1&\triangleq(\lambda_1,\ldots,\lambda_r,1)
\end{align}
と定義する．
また，$1^n\triangleq(1,1,\ldots,1)$（$1$を$n$個並べたもの）と定義する．
アルゴリズムのもととなる数学的性質
\begin{align} P(n,k)=\left(\bigcup_{\lambda\in P(n-1,k-1)}\{\lambda1\}\right)\cup\left(\bigcup_{\lambda\in P(n-k,k)}\{\lambda+{\bf 1}\}\right) \end{align}
$P(n,k)$の元は，末尾が$1$であるものと，末尾が$1$でないものに分けられる．前者は末尾の$1$を消去すると$P(n-1,k-1)$の元になり，後者は各要素から$1$を減じると$P(n-k,k)$の元になる．
疑似コード
procedure $P(n,k)$
if $n=k$ then return $\{1^n\}$ end if;
if $n\leq 0$ or $n< k$ then return $\emptyset$ end if;
$S$←$P(n-1,k-1)$;
$T$←$P(n-k,k)$;
return $\left(\bigcup_{\lambda\in S}\{\lambda1\}\right)\cup\left(\bigcup_{\lambda\in T}\{\lambda+{\bf 1}\}\right)$
end procedure
