Número de combinaciones posibles

Question

¿Cuántas combinaciones posibles de las variables a,b,c,d,e son posibles si sé que:

a+b+c+d+e = 500

y que todos son números enteros y >= 0, entonces sé que son finitos.

Answer 1

@Torlack, @Jason Cohen:La recursión es una mala idea aquí, porque hay "subproblemas superpuestos". Es decir, si eliges a como 1 y b como 2, entonces te quedan 3 variables que deberían sumar 497;llegas al mismo subproblema eligiendo a como 2 y b como 1.(El número de coincidencias de este tipo se dispara a medida que crecen las cifras).

La forma tradicional de atacar este problema es programación dinámica:construya una tabla de abajo hacia arriba con las soluciones a los subproblemas (comenzando con "¿cuántas combinaciones de 1 variable suman 0?") y luego aumente a través de la iteración (la solución a "¿cuántas combinaciones de norte las variables suman k?" es la suma de las soluciones de "¿cuántas combinaciones de n-1 las variables suman j?" con 0 <= j <= 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

La respuesta a tu pregunta es 2656615626.

Aquí está el código que genera la respuesta:

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

En tu caso, summands es 5 y sum es 500.

Tenga en cuenta que este código es lento..Si necesita velocidad, almacene en caché los resultados de summand,sum pares.

Supongo que quieres números >=0.Si quieres >0, reemplace la inicialización del bucle con a = 1 y la condición del bucle con a < sum.También supongo que quieres permutaciones (p. ej. 1+2+3+4+5 más 2+1+3+4+5 etc).Podrías cambiar el bucle for si quisieras a >= b >= c >= d >= e.

Answer 3

Resolví este problema para mi papá hace un par de meses... extiéndelo para tu uso.Estos tienden a ser problemas únicos, así que no opté por los más reutilizables...

a+b+c+d = suma

i = número de combinaciones

        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 4

En realidad, esta sería una buena pregunta para hacer en una entrevista, ya que es lo suficientemente simple como para escribirla en una pizarra, pero lo suficientemente compleja como para hacer tropezar a alguien si no piensa con suficiente atención en ello.Además, también puede obtener dos respuestas diferentes, lo que hace que la implementación sea bastante diferente.

El orden importa
Si el orden importa, entonces cualquier solución debe permitir que aparezca cero para cualquiera de las variables;por lo tanto, la solución más sencilla sería la siguiente:

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

Que devuelve 2656615626.

El orden no importa
Si el orden no importa, entonces la solución no es mucho más difícil, ya que sólo hay que asegurarse de que cero no sea posible a menos que ya se haya encontrado la suma.

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

Que devuelve 2573155876.

Answer 5

Una forma de ver el problema es la siguiente:

Primero, a puede tener cualquier valor entre 0 y 500.Entonces si se deduce que b+c+d+e = 500-a.Esto reduce el problema en una variable.Repita hasta terminar.

Por ejemplo, si a es 500, entonces b+c+d+e=0, lo que significa que para el caso de a = 500, solo hay una combinación de valores para b,c,d y e.

Si a es 300, entonces b+c+d+e=200, que de hecho es el mismo problema que el problema original, solo que reducido en una variable.

Nota:Como señala Chris, ésta es una forma horrible de intentar resolver el problema.

Texto del enlace

Answer 6

Si son números reales entonces infinitos...de lo contrario es un poco más complicado.

(Está bien, para cualquier representación informática de un número real habría un recuento finito...¡pero sería grande!)

Answer 7

Tiene fórmulas generales, si
a + b + c + d = norte
Entonces el número de soluciones integrales no negativas será C(N + number_of_variable - 1, N)

Answer 8

La respuesta de @Chris Conway es correcta.Lo he probado con un código simple que es adecuado para sumas más pequeñas.

                    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 9

La respuesta en matemáticas es 504!/(500!* 4!).

Formalmente, para x1+x2+...xk=n, el número de combinación del número no negativo x1,...xk es el coeficiente binomial:(k-1) -combinación de un conjunto que contiene (n+k-1) elementos.

La intuición es elegir (k-1) puntos de (n+k-1) puntos y usar el número de puntos entre dos puntos elegidos para representar un número en x1,..xk.

Perdón por la mala edición matemática de la primera vez que respondí Stack Overflow.

Just a test for code block

Just a test for code block

    Just a test for code block

Answer 10

¿Incluyendo negativos?Infinito.

¿Incluyendo sólo los aspectos positivos?En este caso no se llamarían "enteros", sino "naturales".En este caso...Realmente no puedo resolver esto, ojalá pudiera, pero mis matemáticas están demasiado oxidadas.Probablemente exista alguna forma integral loca de resolver esto.Puedo dar algunos consejos para los expertos en matemáticas.

Siendo x el resultado final, el rango de A sería de 0 a x, el rango de B sería de 0 a (x - a), el rango de C sería de 0 a (x - a - b) y Así que hasta el e.

La respuesta es la suma de todas esas posibilidades.

Estoy tratando de encontrar alguna fórmula más directa en Google, pero hoy tengo muy poco Google-Fu...