[Algorithm] Fast PartitionsP(n) Program 數字拆解

最近在複習數論和微分方程時，正好想到 yoshi 之前有寫過一個數字拆解的程式。當時稍為研究了一下，不過因為忙專案，所以就沒再繼續下去。現在剛好有點閒時間，就把問題重新思考一遍，想到可以有更快的演算法可以加快速度。

演算法 Algorithm 推導過程

數字拆解的意思是一個正整數 n 可以有幾種相加的方法。例如 2 = 2 + 0 = 1 + 1，有兩種加法；3 = 3 + 0 = 2 + 1 = 1 + 1 + 1，有三種拆解法，因此類推下去：

令 f(n) 的值是 n 的拆解總數， g(i,j) 的值是用小於等於 j 的數字來拆解 i 的結果總合，j <= n – i，則：

也就是說，

g(3,2) 就是用 2 以下的數字來拆解 3 的總合。從上述中我們知道總共有兩個可能，分別是 2+1 和 1+1+1，因此 g(3,2) = 2。另外以 g(1,3) 來說，因為 3 大於 1，無法滿足 1 = 3 + n (n≧0) 的等式，所以用 3 來拆解 1 是沒有意義的，同樣用 2 也是。也就是說，用 i 以下的數字拆解 i，只有一種結果：1+0，所以

由此可知，f(n) 等式會變成：

因應這個改變，f(n) 的公式如下：

當我把 f(1) 到 f(20) 各項數字以二元樹的方法排列出來後去剖析，發現在二元樹左半部的分支部份其實是很穩定在成長的，而右分支的部份比較浮動。既然左分支的數字很穩定，那麼我就把左分支的資訊儲存在一維陣列中，長度為 n+1。更重要的是，左分支的數正好依序是 f(0) 到 f(n/2) 的值！因此左分支就不用再煩惱了，我只要把每個介於 0 到 n-1 的數字拆解結果算出來，那麼左分支的值就自動會出現。

至於右分支的部份比較浮動，因此我使用二維陣列來儲存，空間容量大小是

如果再加上左分支耗用的 n + 1 的話，總空間差不多是

在右分支的計算上，原本是還要遞迴地去計算 g(3,2) 的值，但是我的右分支所儲存的資訊並不需要重複計算，只需要拿已經計算好的數值繼續累加上去就可以了，這使得計算的時間從 Ο(n³) 大幅降低到 Ο(n²) 以下。這種差別有點類似以下的例子：

int a[10];
for (int i = 0, k = 0; i < 10; i++, k = 0) {
  for (int j = 1; j < i + 1; j++) {
    k += j;
  }
  a[i] = k;
}
// 和
int a[10];
for (int i = 0, k = 0; i < 10; i++) {
  k += i;
  a[i] = k;
}

最後的結果，重複計算 100 次所花的時間為 30 ms，跑 1000 次約為 120 ms，跑 10000 次約為 1050 ms。所以每跑一次差不多介於 0.1 ms ~ 0.3 ms 之間。另外全部計算完畢後，serie 陣列中所儲存的資訊就是各個數字拆解的結果，所以從 1 到 100 中每個數字拆解也都一併計算完成了。

數字分解程式

Definition:
PartitionsP(n) gives the number p(n) of unrestricted partitions of the integer n. I parsed the result from 1 to 20, and listed all in the form of binary tree. Then I found that the numbers of left side increase stably. So I wrote this program in Java to count PartiotionsP(n).

/*
 * @(#)PartitionsP.java 04/03/12
 * 
 * Copyright Joseph S. Kuo (a.k.a. CyberJos)
 */

public class PartitionsP {
  public static void main(String[] args) {
    int num = args.length == 1 ? Integer.parseInt(args[0]) : 100;
    System.out.println("Result: " + count(num));
  }

  public static int count(int num) {
    int tableSize = num > 6 ? num - 6 : 1;
    int[][] table = new int[tableSize][(tableSize+1)/2];
    int[] serie = new int[num + 1];
    int leftTotal = 1, rightTotal = 1;

    serie[0] = 1;
    for(int i = 1; i <= num; i++) {
      if (i % 2 == 0) {
        leftTotal += serie[i / 2];
      }

      serie[i] = leftTotal;
      if (i > 2) {
        rightTotal = 1;
        for (int j = i/2+1, k = (i-7)/2; j <= i-2; j++, k--) {
          if (j == i - 2) {
            rightTotal += i/2;
          } else if (i > 6) {
            table[i-7][k] = (j == i-3 ? (i-1)/2 : table[i-8][k-1])
                + (k+3-(j+1)/2 >= 0 ? serie[(2*j+1)/2-(k+3)] : table[j-7][k]);
            rightTotal += table[i-7][k];
          }
        }
        serie[i] += rightTotal;
      }
    }
    return serie[num];
  }
}