如何使用n，m，k改善整数分区? [英] How to improve integer partitioning with n,m,k?

问题描述

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

My program counts the integer partitions of n, which have k distinct partition elements, each is smaller or equal to m. How can I improve the performance? I already cache intermediate results.

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

推荐答案

递归算法

• n 正整数；
• max 最大被请求数；
• return 整数分区中每个加数不超过最大值的部分.

Recursive algorithm

• n the positive integer;
• max the maximum summand size;
• return the part of the integer partition where each summand does not exceed the maximum value.

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

This variant has no useless recursive calls.

// 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中的整数分区}

这篇关于如何使用n，m，k改善整数分区?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！