algorithm
整数パーティションアルゴリズム

整数パーティションアルゴリズムの基本情報

整数の分割は正の整数の和としてそれを書く方法です。たとえば、番号5のパーティションは次のとおりです。

• 5
• 4 + 1
• 3 + 2
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

要約の順序を変更しても、異なるパーティションは作成されません。

パーティション関数は本質的に本質的に再帰的である。なぜなら、より小さい数の結果がより大きい数の結果の構成要素として現れるからである。 pは（n、m）は M以下である正の整数のみを使用して、n個の分割数とします。 m > nについて、 p（n） = p（n、n） 、またp（n、m） = p（n、n） = p（n）であることが分かる。

整数パーティションアルゴリズムの例：

補助空間： O(n^2)
時間複雑度： O(n(logn))

C＃でのInterger分割アルゴリズムの実装

 public class IntegerPartition
{
    public static int[,] Result = new int[100,100];

    private static int Partition(int targetNumber, int largestNumber)
    {
        for (int i = 1; i <= targetNumber; i++)
        {
            for (int j = 1; j <= largestNumber; j++)
            {
                if (i - j < 0)
                {
                    Result[i, j] = Result[i, j - 1];
                    continue;
                }
                Result[i, j] = Result[i, j - 1] + Result[i - j, j];
            }
        }
        return Result[targetNumber, largestNumber];
    }

    public static int Main(int number, int target)
    {
        int i;
        for (i = 0; i <= number; i++)
        {
            Result[i, 0] = 0;
        }
        for (i = 1; i <= target; i++)
        {
            Result[0, i] = 1;
        }
        return Partition(number, target);
    }
}