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

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

演算法 Algorithm 推導過程

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

\[ \begin{aligned} 1 &= 1 + 0\\ 2 &= 2 + 0 = 1 + 1\\ 3 &= 3 + 0 = 2 + 1 = 1 + 1 + 1\\ 4 &= 4 + 0 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1\\ 5 &= 5 + 0 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 \end{aligned} \]

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

\[ \left\{ \begin{aligned} f(0) &= 1 \\ f(n) &= 0, n \in \mathbb{N}^- \\ f(n) &= \sum_{i=0}^{n-1}{g(i,n-i)}, n \in \mathbb{N}^+ \end{aligned} \right. \]

也就是說,

\[ \begin{aligned} f(2) &= g(0,2) + g(1,1) \\ f(3) &= g(0,3) + g(1,2) + g(2,1) \\ f(4) &= g(0,4) + g(1,3) + g(2,2) + g(3,1) \\ f(5) &= g(0,5) + g(1,4) + g(2,3) + g(3,2) + g(4,1) \end{aligned} \]

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,所以

\[ g(1,3) =g(1,2) + g(1,1) = 0 + g(1,1) = 1 \]

由此可知,f(n) 等式會變成:

\[ \begin{aligned} f(2) &= g(0,0) + g(1,1) \\ f(3) &= g(0,0) + g(1,1) + g(2,1) \\ f(4) &= g(0,0) + g(1,1) + g(2,2) + g(3,1) \\ f(5) &= g(0,0) + g(1,1) + g(2,2) + g(3,2) + g(4,1) \end{aligned} \]

因應這個改變,f(n) 的公式如下:

\[ f(n) = \sum_{i=0}^{n-1}{g(i,\min(n-i,i))}, n \in \mathbb{N}^+ \]

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

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

\[ \frac{(n-6)(n-5)}{2} \]

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

\[ n + 1 + \frac{n^2 – 11n +30}{2} = \frac{n^2 – 9n + 32}{2} \]

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

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];
  }
}

Leave a Comment

Your email address will not be published. Required fields are marked *

2 × 4 =

Scroll to Top