Количество возможных комбинаций

Question

Сколько возможных комбинаций переменных a, b, c, d, e возможны, если я знаю, что:

a+b+c+d+e = 500

и что все они являются целыми числами и> = 0, поэтому я знаю, что они конечны.

Answer 1

@ Torlack, @Jason Cohen: Рекурсия - плохая идея, потому что есть «перекрывающиеся подзадачи». Т.е., если вы выберете a в качестве 1 и b в качестве 2, то у вас останется 3 переменные, которые должны добавить до 497; вы получите ту же подзадачу, выбрав a как 2 и b как 1. (Число таких совпадений увеличивается по мере роста числа.)

Традиционным способом решения такой проблемы является динамическое программирование : составьте таблицу снизу вверх решений для подзадач (начиная с того, сколько комбинаций из 1 переменной составляет до 0? ") затем построение путем итерации (решение" сколько комбинаций n переменных в сумме составляет k ? "представляет собой сумму решений для" сколько комбинаций n-1 переменные в сумме составляют j ? "с 0 <= <em>j <= <em>k ).

public static long getCombos( int n, int sum ) {
  // tab[i][j] is how many combinations of (i+1) vars add up to j
  long[][] tab = new long[n][sum+1];
  // # of combos of 1 var for any sum is 1
  for( int j=0; j < tab[0].length; ++j ) {
    tab[0][j] = 1;
  }
  for( int i=1; i < tab.length; ++i ) {
    for( int j=0; j < tab[i].length; ++j ) {
      // # combos of (i+1) vars adding up to j is the sum of the #
      // of combos of i vars adding up to k, for all 0 <= k <= j
      // (choosing i vars forces the choice of the (i+1)st).
      tab[i][j] = 0;
      for( int k=0; k <= j; ++k ) {
        tab[i][j] += tab[i-1][k];
      }
    }
  }
  return tab[n-1][sum];
}

$ time java Combos
2656615626

real    0m0.151s
user    0m0.120s
sys 0m0.012s

Answer 2

Ответ на ваш вопрос: 2656615626 .

Вот код, который генерирует ответ:

public static long getNumCombinations( int summands, int sum )
{
    if ( summands <= 1 )
        return 1;
    long combos = 0;
    for ( int a = 0 ; a <= sum ; a++ )
        combos += getNumCombinations( summands-1, sum-a );
    return combos;
}

В вашем случае summands равно 5, а sum равно 500.

Обратите внимание, что этот код медленный . Если вам нужна скорость, кешируйте результаты от summand,sum пар.

Полагаю, вам нужны цифры >=0. Если вы хотите >0, замените инициализацию цикла на a = 1 и условие цикла на a < sum. Я также предполагаю, что вы хотите перестановки (например, 1+2+3+4+5 плюс 2+1+3+4+5 и т. Д.). Вы можете изменить цикл for, если хотите a >= b >= c >= d >= e.

Answer 3

На самом деле это хороший вопрос, который нужно задать на собеседовании, поскольку он достаточно прост, чтобы вы могли записать его на белой доске, но достаточно сложен, чтобы он мог кого-то сбить с толку, если он не подумает об этом. Кроме того, вы также можете получить два разных ответа, из-за которых реализация будет совершенно разной.

Вопросы заказа
Если порядок имеет значение, то любое решение должно допускать появление нуля для любой из переменных; Таким образом, наиболее прямолинейное решение будет следующим:

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 0; a <= 500; a++) {
            for (int b = 0; b <= (500 - a); b++) {
                for (int c = 0; c <= (500 - a - b); c++) {
                    for (int d = 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

Что возвращает 2656615626.

Порядок не имеет значения
Если порядок не имеет значения, то решение не намного сложнее, поскольку вам просто нужно убедиться, что ноль невозможен, если сумма уже не найдена.

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 1; a <= 500; a++) {
            for (int b = (a != 500) ? 1 : 0; b <= (500 - a); b++) {
                for (int c = (a + b != 500) ? 1 : 0; c <= (500 - a - b); c++) {
                    for (int d = (a + b + c != 500) ? 1 : 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

Что возвращает 2573155876.

Answer 4

Я решил эту проблему для моего отца пару месяцев назад ... продлил для вашего использования. Это, как правило, однократные проблемы, так что я не пошел на самые многоразовые ...

a + b + c + d = сумма

i = количество комбинаций

        for (a=0;a<=sum;a++)
        {
            for (b = 0; b <= (sum - a); b++)
            {
                for (c = 0; c <= (sum - a - b); c++)
                {
                    //d = sum - a - b - c;
                    i++
                }
            }
        }

Answer 5

Один из способов решения проблемы заключается в следующем:

Сначала a может быть любым значением от 0 до 500. Затем, если следует, что b + c + d + e = 500-a. Это уменьшает проблему на одну переменную. Рекурсировать, пока не сделано.

Например, если a равно 500, то b + c + d + e = 0, что означает, что для случая a = 500 существует только одна комбинация значений для b, c, d и e.

Если a равно 300, то b + c + d + e = 200, что фактически является той же проблемой, что и исходная проблема, только уменьшенная на одну переменную.

Примечание. Как указывает Крис, это ужасный способ попытаться решить проблему.

текст ссылки

Answer 6

Ответ по математике - 504! / (500! * 4!).

Формально для x1 + x2 + ... xk = n число комбинаций неотрицательного числа x1, ... xk является биномиальным коэффициентом: (k-1) -комбинация из множества, содержащего (n + k) -1) элементы.

Интуиция заключается в том, чтобы выбрать (k-1) точек из (n + k-1) точек и использовать количество точек между двумя выбранными точками для представления числа в x1, .. xk.

Извините за плохое математическое издание, когда я впервые отвечал на переполнение стека.

Just a test for code block

Just a test for code block

    Just a test for code block

Answer 7

@ Крис Конвей ответ правильный. Я проверил с простым кодом, который подходит для небольших сумм.

                    long counter = 0;
            int sum=25;

            for (int a = 0; a <= sum; a++) {
                for (int b = 0; b <= sum ; b++) {
                    for (int c = 0; c <= sum; c++) {
                        for (int d = 0; d <= sum; d++) {
                             for (int e = 0; e <= sum; e++) {
                           if ((a+b+c+d+e)==sum) counter=counter+1L;

                             }
                       }
                    }
                }
            }
            System.out.println("counter e "+counter);

Answer 8

Имеет общие формулы, если
a + b + c + d = N
Тогда число неотрицательных интегральных решений будет C(N + number_of_variable - 1, N)

Answer 9

Включая негативы? Infinite.

Включая только позитивы? В этом случае их будут называть не «целыми числами», а «натуральными». В этом случае ... Я не могу решить это, хотелось бы, но моя математика слишком ржавая. Вероятно, есть какой-то сумасшедший способ решить эту проблему. Я могу дать несколько советов по математике умелым.

х х конечный результат, диапазон будет от 0 до x, диапазон b будет от 0 до (x - a), диапазон c будет от 0 до (x - a - b), и так далее до е.

Ответ - сумма всех этих возможностей.

Я пытаюсь найти более прямую формулу в Google, но сегодня у меня очень мало Google-Fu ...

Answer 10

Если они действительные числа, то бесконечные ... в противном случае это немного сложнее.

(ОК, для любого компьютерного представления действительного числа будет конечное число ... но оно будет большим!)