Clint Clint - 13 days ago 5
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]

Answer

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

    }

}