Clint - 1 year ago 56
Java Question

# Efficient way to solve "Partition Function Q" or total number of sequences which sum to n

The problem is this: how many sequences can you make with a minimum of 2 numbers where all numbers in the sequence sum to n.

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

Using the equation here* I was able to get the following function:

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

But the time to solve is exponential with n. At around
`n = 180`
it can take 10+ seconds to finish.

I have tried using a hashmap to store previously solved values but I was getting pretty wild results.

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

How can I improve the efficiency in order to generate the total number of sequences faster?

*: In order for the
`GetSequences(n,k)`
function to solve the problem in the link, the result must be subtracted by 1 to account for the sequence
`[n,0]`

You can solve it using memoization. In this approach whenever you solve a subproblem you store the result so that whenever subproblem repeats, you just do a lookup instead of computation.

Below program should give you some idea. Its not an very efficient solution but it does reduce running time considerably.

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

}
``````

}

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download