"Partition Function Q"またはnに合計するシーケンスの合計数を効率的に解決する

Question

問題は次のとおりです。シーケンス内のすべての数値がnになるところで、2つ以上のシーケンスをいくつ作成できますか？

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の指数である：私は次の関数を得ることができた*式hereを使用して

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

。 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)機能ためには、結果はシーケンス[n,0]

Answer 1

のアカウントに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を参照してください。また、特定の型の多項式に対して算術演算を実装する方法のもう1つの有用なウォークスルーについては、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あなたがBigIntegerの使用に切り替えるべき後、n < 770のために良いだろう。

生成関数のアプローチでは、加算値はO(n^2)で、値は最大でQ(n)です。上記と非常によく似たコードは、パーティション関数P(n)、P(n, k)、およびQ(n, k)も同様に計算するために使用できます。