Wählen Sie mehrere Kombination (Matlab)

Question

I 3 Sätze von Array jeweils enthält 12 Elemente gleichen Typs

a=[1 1 1 1 1 1 1 1 1 1 1]; 
b=[2 2 2 2 2 2 2 2 2 2 2]; 
c=[3 3 3 3 3 3 3 3 3 3 3]; 

ich finden müssen, wie viele Möglichkeiten es aufgenommen werden kann, wenn ich zur Abholung benötigen 12 Punkte a Zeit

here, 1 1 2 is same as 2 1 1 

fand ich diesen Link Generating all combinations with repetition using MATLAB.

Dies kann in Matlab innerhalb einer angemessenen Zeit erfolgen.

ist auf diese Weise richtig

abc=[a b c]; 
allcombs=nmultichoosek(abc,12); 
combs=unique(allcombs,'rows'); 

Answer 1

Wenn Sie nur die Anzahl der Wege zu finden, müssen die Elemente auszuwählen, dann mit erzeugenden Funktionen ein Weg ist, um sehr effizient, dass zu berechnen, selbst für ziemlich große Werte von N und k.

Wenn Sie nicht vertraut mit der Erzeugung von Funktionen sind, können Sie hier auf der Mathematik Hintergrund nachlesen:

http://mathworld.wolfram.com/GeneratingFunction.html

und hier:

http://math.arizona.edu/~faris/combinatoricsweb/generate.pdf

Die Lösung auf der Tatsache, Scharnieren dass die Anzahl der Möglichkeiten zur Auswahl k Artikel von 36, mit jeweils 3 Artikel 12 Mal wiederholt, kann aus dem Produkt der generierenden Funktion ermittelt werden:

g(x) = 1 + x + x^2 + x^3 + ... + x^12 

mit sich 3 Mal. Die 12 kommt von der Tatsache, dass die Elemente 12 Mal wiederholt werden (NICHT von der Tatsache, dass Sie 12 wählen), und multiplizieren von selbst 3 Mal ist, weil es drei verschiedene Sätze von Elementen gibt. Die Anzahl der Möglichkeiten, 12 Elemente auszuwählen, ist dann nur der Koeffizient der Potenz von x^12 in diesem Polynomprodukt (versuchen Sie es für kleinere Beispiele, wenn Sie sich selbst beweisen wollen, dass es funktioniert).

Das Tolle an diesem ist, dass MATLAB eine einfache Funktion conv zur Multiplikation Polynome hat:

>> g = ones(1,13); %% array of 13 ones, for a 12th degree polynomial with all `1` coefficents 
>> prod = conv(g, conv(g, g)); %% multiply g by itself 3 times, as a polynomial 
>> prod(13) 
ans = 
    91 

So gibt es 91 Möglichkeiten, 12 Elemente aus der Liste der 36 wählen Wenn Sie 11 Elemente auswählen möchten , das ist z(12) = 78. wenn Sie 13 Elemente auswählen möchten, dass z(14) = 102.

ist schließlich, wenn Sie eine unterschiedliche Anzahl von Elementen in den Sätzen hatte, sagen wir 10 1 's, 12 2' s und 14 3 ist, dann würdest du ha ve 3 verschiedene Polynome der gleichen Form, 1 + x + x^2 + ..., mit Grad 10, 12 und 14 jeweils. Wenn Sie den Koeffizienten des Grads k erneut prüfen, erhalten Sie die Anzahl der Möglichkeiten, k Elemente aus diesem Satz zu wählen.