Nombre de combinaisons possibles

Question

Combien de combinaisons possibles des variables a, b, c, d, e sont possibles si je sais que:

a+b+c+d+e = 500 

et qu'ils sont tous les entiers et> = 0, donc je sachez qu'ils sont finis.

Answer 1

@ Torlack, @Jason Cohen: La récursion est une mauvaise idée ici, car il y a des "sous-problèmes qui se chevauchent". Si vous choisissez a comme 1 et b comme 2, alors vous avez 3 variables restantes qui devraient totaliser 497; vous arrivez au même sous-problème en choisissant a comme 2 et b comme 1.

La manière traditionnelle d'attaquer un tel problème est dynamic programming: construire une table ascendante des solutions aux sous-problèmes (commençant par "combien de combinaisons de 1 variable ajouter jusqu'à 0? ") Puis construire par itération (la solution à" combien de combinaisons de n variables ajouter jusqu'à k? "Est la somme des solutions à" combien de combinaisons de n- 1 les variables ajouter jusqu'à j? » avec 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

Si ce sont des nombres réels alors infinis ... sinon c'est un peu plus compliqué.

(OK, pour une représentation informatique d'un nombre réel, il y aurait un nombre fini ... mais ce serait grand!)

Answer 3

Une façon de regarder le problème est la suivante:

Premièrement, a peut être n'importe quelle valeur de 0 à 500. Ensuite, si b + c + d + e = 500-a. Cela réduit le problème d'une variable. Recurse jusqu'à fait. Par exemple, si a est 500, alors b + c + d + e = 0, ce qui signifie que dans le cas de a = 500, il n'y a qu'une seule combinaison de valeurs pour b, c, d et e. Si a est 300, alors b + c + d + e = 200, ce qui est en fait le même problème que le problème original, juste réduit d'une variable. Remarque: Comme le fait remarquer Chris, c'est une manière horrible d'essayer réellement de résoudre le problème.

link text

Answer 4

Y compris négatifs? Infini.

Y compris seulement les positifs? Dans ce cas, ils ne seraient pas appelés «entiers», mais plutôt «naturels». Dans ce cas ... Je ne peux pas vraiment résoudre ça, j'aurais aimé pouvoir le faire, mais mes calculs sont trop rouillés. Il y a probablement une manière complètement folle de résoudre ceci. Je peux donner quelques conseils pour les maths qualifiés.

étant x le résultat final, la gamme de A serait de 0 à x, la plage de b serait de 0 à (x - a), la gamme C serait de 0 à (x - a - b), et ainsi de suite jusqu'au e.

La réponse est la somme de toutes ces possibilités.

Je suis en train de trouver une formule plus directe sur Google, mais je suis vraiment bas sur mon aujourd'hui Google-Fu ...

Answer 5

La réponse à votre question est 2656615626.

Voici le code qui génère la réponse:

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

Dans votre cas, summands est 5 et sum est 500.

Notez que ce code est lent. Si vous avez besoin de vitesse, cachez les résultats des paires summand,sum. Je suppose que vous voulez les numéros >=0. Si vous voulez >0, remplacez l'initialisation de la boucle par a = 1 et la condition de boucle par a < sum. Je suppose également que vous voulez des permutations (par ex.1+2+3+4+5 plus 2+1+3+4+5 etc). Vous pouvez changer la boucle for si vous voulez a >= b >= c >= d >= e.

Answer 6

J'ai résolu ce problème pour mon père il y a quelques mois ... étendre pour votre usage. Ceux-ci ont tendance à être un problème de temps, donc je ne suis pas allé pour la plupart ... réutilisable

a + b + c + d = somme

i = nombre de combinaisons

 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 7

Ce serait effectivement une bonne question à poser sur une entrevue car il est assez simple que vous pourriez écrire sur un tableau blanc, mais assez complexe qu'il quelqu'un pourrait trébucher si elles ne » Je réfléchis assez à ce sujet. En outre, vous pouvez également utiliser deux réponses différentes, ce qui rend l'implémentation très différente.

Commander Questions
Si les questions d'ordre alors besoin de solution pour permettre zéro à apparaître pour l'une des variables; ainsi, la plus droite solution avant serait la suivante:

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

qui retourne 2656615626.

ordre n'importe
Si l'ordre n'a pas d'importance alors la solution est beaucoup plus difficile que Vous devez juste vous assurer que zéro n'est pas possible, sauf si la somme a déjà été trouvée.

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

qui retourne 2573155876.

Answer 8

Il a des formules générales, si
a + b + c + d = N
Ensuite nombre de solution intégrale non négatif sera C(N + number_of_variable - 1, N)

Answer 9

@ Chris Conway réponse est correcte. J'ai testé avec un code simple qui convient pour les petites sommes.

    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 10

La réponse en maths est 504!/(500! * 4!). Formellement, pour x1 + x2 + ... xk = n, le nombre de combinaison du nombre non négatif x1, ... xk est le coefficient binomial: (k-1) -combinaison d'un ensemble contenant (n + k-1) éléments.

L'intuition est de choisir (k-1) les points de (n + k-1) points et d'utiliser le nombre de points entre deux points choisis pour représenter un nombre dans x1, .. xk. Désolé pour la mauvaise édition de maths pour mon premier temps répondant Stack Overflow.

Just a test for code block

Just a test for code block 

    Just a test for code block