Количество различных групп из N целых чисел, суммирующих до A

Я хочу рассчитать количество разных упорядоченных групп из 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;
}

Я подозреваю, что может быть лучший способ (какой-то математический расчет, который мне не хватает..) есть?

ИЗМЕНИТЬ В исходном вопросе я забыл принять во внимание порядок

Ответ 1

Это комбинаторная композиция из A в N частей (включая нулевые части). Количество композиций для пары (A, N) равно C (A + N - 1, A), где C() представляет собой комбинационное число aka биномиальный коэффициент. См. Ту же формулу здесь и здесь

Ответ 2

Представьте себе большой сегмент длины A. Представьте N-1 упорядоченные разделители, разделив сегмент на части. Следовательно, каждая часть является слагаемым, а весь отрезок - суммой.

Ergo, все, что вам нужно, это просто предоставить алгоритм для перечисления местоположений разделителей.

Первый разделитель можно поместить в любую из позиций N+1 P_0 = {0,1,... N}

Второй разделитель может войти в любой из P_1 = {P_0,... N}

И так далее.

Вы можете использовать рекурсию для ее реализации.

Ответ 3

Я уверен, что для этого есть математический расчет, но поскольку это программирование Q & A, я расскажу вам, как заставить вашу программу быстрее дать ответ: вы можете использовать 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);
}

Ответ 4

Для перечисления: используйте формулу, приведенную в других решениях выше, ПУТЬ БОЛЬШЕ ЭФФЕКТИВНОСТИ. Вы никогда не хотите генерировать полный набор n-целочисленных композиций, если это не требуется. Они несут непреодолимые свойства, особенно если вы хотите только их суммировать, а не генерировать их. Создание их - еще одна проблема...

Для генерации: используйте алгоритм без петли... Есть множество результатов O (1) -серой серой кодовой последовательности. Существует очень мало вариаций ограниченных целых композиций, которые не имеют или не могут иметь петлевых алгоритмов. Многие алгоритмы в этом классе задач для целочисленных композиций, большинство из которых очень специфичны, но существует множество современных алгоритмов без петли, которые существуют для этой конкретной проблемы. Супер эффективный. Грубая сила никогда не может пойти с этой проблемой, если вы не получите много параллельных вычислений в вашем распоряжении. Google или Google Scholar в вашем распоряжении!: D

Надеюсь, это поможет!

Ответ 5

Я нашел другое решение, просто с рекурсией и без разделителей:

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("");
    }
}

}