解決「分區函數Q」或總和爲n的序列總數的有效方法

Question

問題是：如果序列中的所有數字總和爲n，最少2個數字可以產生多少個序列。

http://mathworld.wolfram.com/PartitionFunctionQ.html

使用方程here *我能得到以下功能：

public static int GetSequences(int n, int k) { 
    if(n <= k) return 0; 
    int result = 1; 
    for(int i = k + 1; i < n; i++) { 
     result += GetSequences(n - i, i); 
    } 
    return result; 
} 

但解決時間指數有n。在n = 180左右，完成時間可能需要10秒以上。

我已經嘗試使用散列表來存儲以前解決的值，但我得到非常野生的結果。

static Map<Long,Long> cache = new HashMap<Long,Long>(); 

public static int solve(int n) { 
    for(int i = 3; i <= n; i++) { 
     cache.put((long)i, (long)GetSequences(i, 0)); 
    } 
    return cache.get((long) n).intValue() - 1; 
} 

public static int GetSequences(int n, int k) { 
    if(n <= k) return 0; 
    if(cache.containsKey((long)k)) { 
     return cache.get((long)k).intValue(); 
    } 
    int result = 1; 
    for(int i = k + 1; i < n; i++) { 
     result += GetSequences(n - i, i); 
    } 
    return result; 
} 

如何提高效率以便更快地生成序列總數？

*：爲了使GetSequences(n,k)功能，解決了鏈路的問題，其結果必須由1減去到帳戶的序列[n,0]

Answer 1

您可以使用記憶化解決它。在這種方法中，每當你解決一個子問題時，你都要存儲結果，以便每當子問題重複時，你只需要進行查找而不是計算。

下面的程序應該給你一些想法。它不是一個非常有效的解決方案，但它大大減少了運行時間。

public class Partition { 
    public static void main(String[] args) { 
     System.out.println(GetSequences(180, 1, new HashMap<>())); 
    } 

    public static int GetSequences(int n, int k, Map<Pair, Integer> data) { 
     if (n <= k) 
      return 0; 

     int result = 1; 

     for (int i = k + 1; i < n; i++) { 
      Pair p = new Pair(n - i, i); 
      if (data.containsKey(p)) { 
       result += data.get(p); 
      } else { 
       int res = GetSequences(n - i, i, data); 
       data.put(p, res); 
       result += res; 
      } 
     } 
     return result; 
    } 

    static class Pair { 
     int n; 
     int k; 

     Pair(int n, int k) { 
      this.n = n; 
      this.k = k; 
     } 

     @Override 
     public int hashCode() { 
      final int prime = 31; 
      int result = 1; 
      result = prime * result + k; 
      result = prime * result + n; 
      return result; 
     } 

     @Override 
     public boolean equals(Object obj) { 
      if (this == obj) 
       return true; 
      if (obj == null) 
       return false; 
      if (getClass() != obj.getClass()) 
       return false; 
      Pair other = (Pair) obj; 
      if (k != other.k) 
       return false; 
      if (n != other.n) 
       return false; 
      return true; 
     } 

    } 

}

Answer 2

您也可以完全放棄遞歸和使用Mathworld頁面，這歸結爲多項式算法上顯示的生成功能。請參閱here以獲取我在下面重新制作的解釋和Java實現。此外，請參閱here和here以瞭解如何實現特定類型多項式的算術的另一個有用的演練。

static long Q(int n) { 
    return QArray(n)[n]; 
} 

// Computes Q(i) for i = 0..n 
// 
// The following implementation uses the generating function: 
// 
//  Sum (Q(i)*x^i) = Product (1 + x^t) 
// 
// for i = 0,1,2... and t = 1,2,3... 
// 
// `poly` below is an array of coefficients for x^0,x^1,x^2...x^n. 
// Terms above x^n in the infnite series are ignored. 
static long[] QArray(int n) { 
    assert n >= 0: n; 

    long[] poly = new long[n + 1]; 
    poly[0] = 1; 

    for (int t = 1; t <= n; t++) 
     for (int exp = n; exp >= t; exp--) // multiply by (1 + x^t) 
      poly[exp] += poly[exp - t]; 

    return poly; 
} 

一個long將有利於n < 770，之後您應該切換到使用BigInteger。

生成函數的方法需要O(n^2)添加和足夠的空間來存儲值高達Q(n)。與上述非常類似的代碼也可用於計算分區函數P(n),P(n, k)和Q(n, k)。