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 des entiers et >= 0, donc je sais qu'ils sont finis.

Answer 1

@Torlack, @Jason Cohen :La récursivité est une mauvaise idée ici, car il y a des «sous-problèmes qui se chevauchent». C'est-à-dire si tu choisis a comme 1 et b comme 2, alors il vous reste 3 variables qui devraient totaliser 497 ;vous arrivez au même sous-problème en choisissant a comme 2 et b comme 1.(Le nombre de telles coïncidences explose à mesure que les chiffres augmentent.)

La manière traditionnelle d’aborder un tel problème est programmation dynamique:construire un tableau ascendant des solutions aux sous-problèmes (en commençant par « combien de combinaisons de 1 variable totalisent 0 ? »), puis en construisant par itération (la solution à « combien de combinaisons de n les variables totalisent k?" est la somme des solutions de "combien de combinaisons de n-1 les variables totalisent 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

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 ton cas, summands est 5 et sum est 500.

Notez que ce code est lent.Si vous avez besoin de vitesse, mettez en cache les résultats de summand,sum paires.

Je suppose que tu veux des chiffres >=0.Si tu veux >0, remplacez l'initialisation de la boucle par a = 1 et la condition de boucle avec 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 le souhaitez a >= b >= c >= d >= e.

Answer 3

J'ai résolu ce problème pour mon père il y a quelques mois... prolongez-le pour votre usage.Il s'agit généralement de problèmes ponctuels, donc je n'ai pas opté pour les plus réutilisables...

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 4

Ce serait en fait une bonne question à poser lors d'un entretien, car elle est suffisamment simple pour que vous puissiez l'écrire sur un tableau blanc, mais suffisamment complexe pour que cela puisse faire trébucher quelqu'un s'il n'y réfléchit pas suffisamment.En outre, vous pouvez également obtenir deux réponses différentes, ce qui rend la mise en œuvre très différente.

La commande compte
Si l'ordre est important, toute solution doit permettre à zéro d'apparaître pour l'une des variables ;ainsi, la solution la plus simple 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);
    }
}

Ce qui renvoie 2656615626.

L'ordre n'a pas d'importance
Si l'ordre n'a pas d'importance, la solution n'est pas beaucoup plus difficile car il vous suffit de vous assurer que zéro n'est pas possible à moins que la somme n'ait 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);
    }
}

Ce qui renvoie 2573155876.

Answer 5

Une façon d’aborder le problème est la suivante :

Premièrement, a peut être n’importe quelle valeur comprise entre 0 et 500.Alors s’il s’ensuit que b+c+d+e = 500-a.Cela réduit le problème d’une variable.Récurez jusqu'à ce que vous ayez terminé.

Par exemple, si a vaut 500, alors b+c+d+e=0, ce qui signifie que pour le cas a = 500, il n’existe qu’une seule combinaison de valeurs pour b, c, d et e.

Si a vaut 300, alors b+c+d+e=200, ce qui est en fait le même problème que le problème d'origine, juste réduit d'une variable.

Note:Comme Chris le souligne, c'est une manière horrible d'essayer de résoudre le problème.

texte du lien

Answer 6

S'il s'agit de nombres réels alors infinis...sinon c'est un peu plus compliqué.

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

Answer 7

Il a des formules générales, si
a + b + c + d = N
Alors le nombre de solutions intégrales non négatives sera C(N + number_of_variable - 1, N)

Answer 8

La réponse de @Chris Conway est correcte.J'ai testé avec un code simple qui convient aux 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 9

La réponse en mathématiques est 504!/(500!*4 !).

Formellement, pour x1+x2+...xk=n, le nombre de combinaisons de nombres non négatifs 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) points parmi (n+k-1) points et d'utiliser le nombre de points entre deux points choisis pour représenter un nombre en x1,..xk.

Désolé pour la mauvaise édition mathématique pour ma première réponse à Stack Overflow.

Just a test for code block

Just a test for code block

    Just a test for code block

Answer 10

Y compris les négatifs ?Infini.

Y compris uniquement les points positifs ?Dans ce cas, ils ne seraient pas appelés « entiers », mais « naturels ».Dans ce cas...Je ne peux pas vraiment résoudre ce problème, j'aimerais pouvoir le faire, mais mes calculs sont trop rouillés.Il existe probablement une manière intégrale et folle de résoudre ce problème.Je peux donner quelques conseils aux experts en mathématiques.

Étant x le résultat final, la plage de A serait de 0 à x, la plage de b serait de 0 à (x - a), la plage de C serait de 0 à (x - a - b), et ainsi avant le e.

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

J'essaie de trouver une formule plus directe sur Google, mais je suis vraiment à court de mon Google-Fu aujourd'hui...