Anzahl der möglichen Kombinationen

Question

Wie viele mögliche Kombinationen der Variablen a, b, c, d, e sind möglich, wenn ich weiß, dass:

a+b+c+d+e = 500

, und dass sie alle ganzen Zahlen und> = 0, so dass ich weiß, sie sind endlich.

Answer 1

@Torlack, @ Jason Cohen: Rekursion ist eine schlechte Idee, hier, weil es „überlappende Teilprobleme.“ Das heißt, wenn Sie a als 1 und b als 2 wählen, dann haben Sie drei Variablen, sollten addiert 497 nach links; erreichen Sie die gleiche Subproblem an, indem Sie a als 2 und b als 1. (Die Zahl solcher Zufälle explodiert wie die Zahlen wachsen.)

Der traditionelle Weg, ein solches Problem zu attackieren ist dynamische Programmierung : einen Tisch bauen Bottom up der Lösungen für die Teilprobleme (beginnend mit „wie viele Kombinationen von 1 Variable auf 0 aufsummieren?“) dann durch Iteration Aufbau (die Lösung „, wie viele Kombinationen von n Variablen hinzufügen bis zu k ?“ist die Summe der Lösungen " wie viele Kombinationen von n-1 Variablen hinzufügen bis zu j ?" mit 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

Die Antwort auf Ihre Frage lautet 2656615626 .

Hier ist der Code, der die Antwort erzeugt:

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

In Ihrem Fall summands 5 und sum 500.

Beachten Sie, dass dieser Code nur langsam . Wenn Sie Geschwindigkeit benötigen, Cache, um die Ergebnisse von summand,sum Paaren.

Ich nehme an, Sie Zahlen >=0 wollen. Wenn Sie >0 wollen, ersetzen Sie die Schleife Initialisierung mit a = 1 und der Schleifenbedingung mit a < sum. Ich nehme an, Sie wollen auch Permutationen (z 1+2+3+4+5 Plus 2+1+3+4+5 usw.). Sie könnten die for-Schleife ändern, wenn Sie a >= b >= c >= d >= e wollte.

Answer 3

Ich löste dieses Problem für meinen Vater vor ein paar Monaten ... verlängern für Ihren Einsatz. Diese neigen dazu, eine Zeit Probleme zu sein, damit ich nicht für die meisten wiederverwendbar ging ...

a + b + c + d = Summe

i = Anzahl der Kombinationen

        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

Das wäre eigentlich eine gute Frage zu einem Interview zu fragen, wie es ist einfach genug, dass man auf eine weiße Tafel schreiben könnte, aber komplex genug, dass es jemand darüber stolpern kann, wenn sie nicht denken, sorgfältig genug darüber. Auch Sie können auch für zwei unterschiedliche Antworten, die die Umsetzung ganz anders führen.

Auftrag Matters
Wenn die Auftragsangelegenheiten dann eine Lösung für Null ermöglichen, muss für eine der Variablen zu erscheinen; somit ist die direkteste Lösung wäre wie folgt:

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

Welche 2656615626 zurück.

Bestellung spielt keine Rolle,
Wenn die Reihenfolge keine Rolle spielt, dann ist die Lösung nicht, dass es sehr viel schwieriger, wie Sie müssen nur sicherstellen, dass Null nicht möglich ist, es sei denn Summe bereits gefunden worden ist.

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

Welche 2573155876 zurück.

Answer 5

Eine Möglichkeit, das Problem zu betrachten, ist wie folgt:

Erstens kann ein beliebiger Wert sein, von 0 bis 500. Dann folgt, dass, wenn b + c + d + e = 500-a. Dadurch verringert sich das Problem durch eine Variable. Rekursion bis getan.

Wenn beispielsweise ein 500 ist, b + c + d + e = 0, was bedeutet, dass für den Fall von a = 500, gibt es nur eine Kombination von Werten für b, c, d und e.

Wenn ein 300 ist, b + c + d + e = 200, die in der Tat ist das gleiche Problem wie das ursprüngliche Problem, nur reduziert, indem eine Variable.

. Hinweis: Wie Chris weist darauf hin, das ist eine schreckliche Art und Weise tatsächlich das Problem zu lösen versuchen,

Link-Text

Answer 6

Wenn sie eine reelle Zahlen dann unendlich sind ... sonst ist es ein bisschen schwieriger.

(OK, für jede Computerdarstellung einer reellen Zahl gäbe es eine endliche Zählung sein ... aber es wäre zu groß!)

Answer 7

Es hat allgemeine Formeln, wenn
a + b + c + d = N
Dann Anzahl der nicht-negativer integraler Lösung wird C(N + number_of_variable - 1, N)

Answer 8

@ Chris Conway Antwort ist richtig. Ich habe mit einem einfachen Code getestet, die für kleinere Beträge geeignet ist.

                    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

Die Antwort in Mathe ist 504! / (500! * 4!).

Formal für x1 + x2 + ... xk = n, die Anzahl der Kombination von nicht-negativer Zahl x1, ... xk ist der Binomialkoeffizient: (k-1) -combination aus einem Satz, enthaltend (n + k -1) Elemente.

Die Intuition wählen (k-1) Punkte von (n + k-1) Punkten und die Anzahl der Punkte zwischen zwei ausgewählten Punkten verwenden, um eine Anzahl in x1 darstellen, .. xk.

Es tut sie Leid über die schlechte Mathe-Ausgabe für mein erstes Mal beantwortet Stack-Überlauf.

Just a test for code block

Just a test for code block

    Just a test for code block

Answer 10

Einschließlich Negativen? Unendlichen.

Einschließlich nur Positives? In diesem Fall würden sie nicht „ganze Zahlen“ genannt werden, sondern „Naturals“, statt. In diesem Fall ... ich dies nicht wirklich lösen kann, ich wünschte, ich könnte, aber meine Mathe ist zu rostig. Es gibt wohl ein paar verrückte integrale Art und Weise, diese zu lösen. Ich kann einige Hinweise für die Mathe geben qualifiziert mich um.

x das Endergebnis ist, Die Reichweite eines würde von 0 bis x sein, Der Bereich von B würde von 0 bis (x - a) sein, Bereich von C würde von 0 bis (x - a - b) sein, und so weiter, bis der e.

Die Antwort ist die Summe aller dieser Möglichkeiten.

Ich versuche, einig direktere Formel auf Google zu finden, aber ich bin wirklich tief auf meinem Google-Fu heute ...