A Simple Generation of Multi-dimensional Partitions

摘要

This paper gives a simple algorithm to generate all multi-dimensional partitions of a positive integer N. The problem is one of the basic problems in combinatorics, and it includes generations of integer partitions and plane partitions. For a given integer d as dimension, our algorithm generates each partition of a given integer in O(d) time for each without repetition. The known algorithm is complicated and includes many "goto" statements, while our algorithm is simple and efficient. Also, we propose an algorithm to generate all exactly d-dimensional partition in O(d) time for each.%本文では，自然数Nの多次元分割を列挙するシンプルなアルゴリズムを提案する．この問題は，整数分割や平面分割の列挙を含む，組合せ論における基本的な問題の1つである．本文では，次元数dが与えられたとき，d次元分割を1つ当たり最悪でもO（d）時間で列挙するアルゴリズムを与える．既存のアルゴリズムは非常に複雑で，多くの“goto”文を含んでいるが，我々のアルゴリズムはシンプルかつ高速である．また，提案したアルゴリズムを改良することにより，ちょうどd次元の分割を1つ当たりO（d）時間で列挙できることを示す．