Clint - 1 year ago 49

Java Question

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`

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)`

`[n,0]`

Answer Source

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

}