如何改进n，m，k的整数分区

Question

我的程序统计n的整数分区，这些分区具有k不同的分区元素，每个分区小于或等于m。如何提高性能？我已经缓存了中间结果。

public long q(int n, int m, int k) {
return q1(n, m, k, 0, 0, new HashMap());
}
private long q1(int n, int m, int k, int level, int last, Map<String, Long> cache) {
if (n < 0) {
return 0;
}
if (level + 1 == k) {
if (n > m) {
return 0;
} else {
return 1;
}
}
int first = (level == 0) ? 1 : last + 1;
long total = 0;
for (int i = first; i <= Math.min(m, n / 2); i++) {
last = i;
if (n - i > 0 && last < n - i) {
String key = n - i + "_" + level + 1 + "_" + last;
Long fetched = cache.get(key);
if (fetched == null) {
fetched = q1(n - i, m, k, level + 1, last, cache);
cache.put(key, fetched);
}
total += fetched;
}
return total;
}

Answer 1

递归算法

• n为正整数
• max是最大被加数大小
• return整数分区中每个被加数不超过最大值的部分

此变体没有无用的递归调用。

// start program
public static void main(String[] args) {
int n = 5, max = 3;
List<int[]> part = partition(n, max);
// output
for (int[] comb : part) System.out.println(Arrays.toString(comb));
}

/**
* @param n   the positive integer
* @param max the maximum summand size
* @return the part of the integer partition,
* where each summand does not exceed the maximum value
*/
public static List<int[]> partition(int n, int max) {
List<int[]> list = new ArrayList<>();
partition(n, max, "", list, new int[0]);
return list;
}

public static void partition(
int i, int max, String indent, List<int[]> master, int[] holder) {
if (i == 0) {
master.add(holder);
System.out.println(indent + "i=" + i + ",max=" + max
+ "    comb=" + Arrays.toString(holder));
}
for (int j = Math.min(max, i); j >= 1; j--) {
int[] temp = Arrays.copyOf(holder, holder.length + 1);
temp[holder.length] = j;
System.out.println(indent + "i=" + i + ",j=" + j + ",max=" + max
+ "  temp=" + Arrays.toString(temp));
partition(i - j, j, indent + "  ", master, temp);
}
}

递归树n=5、max=3:的输出

i=5,j=3,max=3  temp=[3]
i=2,j=2,max=3  temp=[3, 2]
i=0,max=2    comb=[3, 2]
i=2,j=1,max=3  temp=[3, 1]
i=1,j=1,max=1  temp=[3, 1, 1]
i=0,max=1    comb=[3, 1, 1]
i=5,j=2,max=3  temp=[2]
i=3,j=2,max=2  temp=[2, 2]
i=1,j=1,max=2  temp=[2, 2, 1]
i=0,max=1    comb=[2, 2, 1]
i=3,j=1,max=2  temp=[2, 1]
i=2,j=1,max=1  temp=[2, 1, 1]
i=1,j=1,max=1  temp=[2, 1, 1, 1]
i=0,max=1    comb=[2, 1, 1, 1]
i=5,j=1,max=3  temp=[1]
i=4,j=1,max=1  temp=[1, 1]
i=3,j=1,max=1  temp=[1, 1, 1]
i=2,j=1,max=1  temp=[1, 1, 1, 1]
i=1,j=1,max=1  temp=[1, 1, 1, 1, 1]
i=0,max=1    comb=[1, 1, 1, 1, 1]

列表n=5、max=3:的输出

[3, 2]
[3, 1, 1]
[2, 2, 1]
[2, 1, 1, 1]
[1, 1, 1, 1, 1]

---

^{另请参阅：Java中的整数分区}