12

我想计算 N 个整数的不同有序组的数量，以便每个组的元素总和为 A

例如：如果 N = 3 且 A = 3，则结果应为 10：
1 = [3, 0, 0]
2 = [2, 1, 0]
3 = [1, 2, 0]
4 = [0, 3 , 0]
5 = [2, 0, 1]
6 = [1, 1, 1]
7 = [0, 2, 1]
8 = [1, 0, 2]
9 = [0, 1, 2]
10 = [0, 0, 3]

我这样做的方式是蛮力：

public static int calc(int a, int n){
    if (n <= 1 || a == 0) return 1;

    int sum = 0;
    for (int i=0; i<=n; i++)
        sum += calc(a - i, n - 1);

    return sum;
}

我怀疑可能有更好的方法（我错过了一些数学计算..）有吗？

编辑 在最初的问题中，我忘了考虑顺序

4

5 回答 5

5

这是A 到 N 部分（包括零部分）的组合组合。对 (A, N) 的组合数等于 C(A + N - 1, A)，其中 C() 是组合数，即二项式系数。在此处和此处查看相同的公式

于 2012-10-12T16:56:02.210 回答
3

想象一下大段的长度A。想象一下N-1有序的分隔符，将段分成几部分。因此，每个部分都是一个和，而整个段是一个和。

因此，您所需要的只是提供算法来枚举分隔符位置。

您可以将第一个分隔符放入任何N+1位置 P_0={0,1,...N}

第二个分隔符可以进入任何 P_1={P_0,...N}

等等。

您可以使用递归来实现这一点。

于 2012-10-12T12:02:18.067 回答
2

我确信有一个数学计算可以回答这个问题，但由于这是一个编程问答，我会告诉你如何让你的程序更快地给出答案：你可以使用memoization。

calc(a, n)目前，您的程序每次都会重新计算答案。但是，答案可以计算一次，因为它在后续调用中不会改变。为 的结果添加一个 2D 数组calc(a,n)，用 初始化-1，并在计算结果之前使用它来查找结果，以节省大量时间来一遍又一遍地重新计算相同的数字：

private static int[][] memo = new int[30][30];
static {
    for(int i = 0 ; i != 30 ; i++)
        for(int j = 0 ; j != 30 ; j++)
            memo[i][j] = -1;
}
public static int calc(int a, int n){
    if (n <= 1 || a == 0) return 1;
    if (memo[a][n] > 0) return memo[a][n];
    int sum = 0;
    for (int i=0; i<=n; i++)
        sum += calc(a - i, n - 1);
    return (memo[a][n] = sum);
}
于 2012-10-12T10:55:28.537 回答
1

对于枚举：使用上面其他解决方案中给出的公式，更有效。除非需要，否则您永远不想实际生成完整的 n 整数组合。它们带有难以处理的属性，特别是如果您只想汇总它们而不是生成它们。生成它们是另一个问题......

对于生成：使用无环算法......有许多 O(1)-per 格雷码序列结果。很少有限制整数组合的变体没有或可以有无环算法。这类整数组合问题中的许多算法，其中大多数都是非常具体的，但是对于这个特定问题存在大量现代无环算法。超级高效。除非您可以使用大量并行计算，否则蛮力永远不是解决此问题的方法。Google 或 Google Scholar 随时为您服务！:D

希望这可以帮助！

于 2012-12-20T23:55:50.783 回答
0

我找到了另一种解决方案，只是使用递归且没有分隔符：

public class App201210121604 {

public static Vector<int[]> split(int sum, int count) {

    if( sum < 0 ) {
        throw new IllegalArgumentException("Negative sum is not allowed");
    }

    Vector<int[]> ans = new Vector<int[]>();

    // "reserved" end of recursion
    if( count <= 0 ) {
        // nothing to do
    }

    // end of recursion
    else if( count == 1 ) {
        ans.add(new int[] {sum});
    }

    // body of recursion
    else {
        // for each first summand from 0 to summ
        for(int i=0; i<=sum; ++i) {

            // do a recursion to get the "tail"
            for(int[] tail : split(sum-i, count-1)) {

                int[] group = new int[count];
                group[0] = i;
                System.arraycopy(tail, 0, group, 1, count-1);

                ans.add(group);
            }
        }
    }

    return ans;
}

public static void main(String[] args) {

    Vector<int[]> ans = split(8, 4);

    for(int[] group : ans) {
        for(int i=0; i<group.length; ++i) {
            if( i>0 ) System.out.print("+");
            System.out.print(group[i]);
        }
        System.out.println("");
    }
}

}
于 2012-10-12T14:18:08.817 回答