Zeit für eine weitere leichte Herausforderung, an der alle teilnehmen können!

Der multinomiale Satz besagt:

Der Ausdruck in Klammern ist der Multinomialkoeffizient, definiert als:

Wenn man zulässt, dass die Terme k _i über alle ganzzahligen Partitionen von n reichen, erhält man das n- te Niveau von Pascals m- Simplex. Ihre Aufgabe ist es, diesen Koeffizienten zu berechnen.

Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die m Zahlen, n , k ₁ , k ₂ , ..., k _m-1 annimmt und den entsprechenden Multinomialkoeffizienten ausgibt oder zurückgibt. Ihr Programm kann gegebenenfalls m als zusätzliches Argument verwenden. Beachten Sie, dass k _m nicht in der Eingabe ist.

• Diese Zahlen können in einem beliebigen Format eingegeben werden, zum Beispiel in Listen gruppiert oder in Unary oder irgendetwas anderem codiert, solange die eigentliche Berechnung des Multinomialkoeffizienten von Ihrem Code durchgeführt wird und nicht der Codierungsprozess.

• Das Ausgabeformat ist ähnlich flexibel.

• Der gesamte Code sollte in weniger als einer Minute für n und m bis 1000 ausgeführt werden.

• Sorgen Sie sich nicht um einen Ganzzahlüberlauf.

• Integrierte Funktionen zur Berechnung des Multinomialkoeffizienten sind nicht zulässig.

• Es gelten Standardlücken.

Wertung

Das ist Codegolf: Kürzeste Lösung in Bytes gewinnt.

Testfälle

Input: 3, [2, 0]
Output: 3

Input: 3, [1, 1]
Output: 6

Input: 11, [1, 4, 4]
Output: 34650

Input: 4, [1,2]
Output: 12

Input: 15, [5,4,3,2]
Output: 37837800

Input: 95, [65,4,4]
Output: 1934550571913396675776550070308250

Input: 32, [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
Output: 4015057936610313875842560000000

Input: 15, [3,3,3,3]
Output: 168168000

Input: 1000, [10,10,10,10,10,10,10,10,10,10,100,100,100,100,100,100,100,100]
Output: 1892260836114766064839886173072628322819837473493540916521650371620708316292211493005889278395285403318471457333959691477413845818795311980925098433545057962732816261282589926581281484274178579110373517415585990780259179555579119249444675675971136703240347768185200859583936041679096016595989605569764359198616300820217344233610087468418992008471158382363562679752612394898708988062100932765563185864346460326847538659268068471585720069159997090290904151003744735224635733011050421493330583941651019570222984959183118891461330718594645532241449810403071583062752945668937388999711726969103987467123014208575736645381474142475995771446030088717454857668814925642941036383273459178373839445456712918381796599882439216894107889251444932486362309407245949950539480089149687317762667940531452670088934094510294534762190299611806466111882595667632800995865129329156425174586491525505695534290243513946995156554997365435062121633281021210807821617604582625046557789259061566742237246102255343862644466345335421894369143319723958653232683916869615649006682399919540931573841920000000000000

Input: 33, [17]
Output: 1166803110

Input: 55, [28]
Output: 3824345300380220

Gelee , 7 6 Bytes

;_/!:/

Schau ma, kein Unicode! Dieses Programm verwendet eine einzelne Liste als Eingabe, wobei sich n am ersten Index befindet.

Probieren Sie es online! oder überprüfen Sie alle Testfälle auf einmal .

Wie es funktioniert

;_/!:/ Input: A (list)

 _/    Reduce A by subtraction. This subtracts all other elements from the first.
;      Concatenate A with the result to the right.
   !   Apply factorial to all numbers in the resulting list.
    :/ Reduce the result by division. This divides the first element by the others.

CJam, 11 Bytes

l~_:-+:m!:/

Eingabe als einzelne Liste mit nzuerst:

[95 65 4 4]

Diese Griffe gibt bis zu nund m1000 so ziemlich sofort.

Teste es hier.

Erläuterung

l~  e# Read a line of input and evaluate it.
_   e# Duplicate.
:-  e# Fold subtraction over the list. A fold is essentially a foreach loop that starts
    e# from the second element. Hence, this subtracts all the k_i from n, giving k_m.
+   e# Append k_m to the list.
:m! e# Compute the factorial of each element in the list.
:/  e# Fold division over the list. Again, this divides n! by each of the k_i!.

MATL , 21 15 Bytes

Lassen Sie uns die Log-Gamma-Funktion sinnvoll einsetzen. Dies vermeidet internes Überlaufen, indem mit Logarithmen von Fakultäten gearbeitet wird, nicht mit Fakultäten selbst.

1+ZgiO$Gs-h1+Zgs-ZeYo

Dies funktioniert in der aktuellen Version (9.2.2) der Sprache / des Compilers, die / der früher als diese Herausforderung ist.

Eingaben sind: zuerst eine Zahl, dann ein numerischer Vektor. Das Ergebnis wird als erzeugt double, was die maximale Ausgabe auf irgendwo begrenzt 2^52.

Beispiel

>> matl 1+ZgiO$Gs-h1+Zgs-ZeYo
> 15
> [5 4 3 2]
37837800

Erläuterung

1+       % implicit input (number). Add 1
Zg       % log-gamma function
i        % input (numeric vector).
0$G      % push both inputs
s-       % sum the second input (vector) and subtract from first
h1+      % append to vector. Add 1
Zg       % log-gamma function, element-wise on extended vector
s        % sum of results
-        % subtract from previous result of log-gamma
Ze       % exponential
Yo       % round. Implicit display

PowerShell, 91 bis 74 Byte

_{Woo! Meine 100. Antwort auf PPCG!}

param($n,$k)(1..$n-join'*'|iex)/(($k|%{$n-=$_;1..$_})+(1..$n)-join'*'|iex)

Wütend. Den kürzesten Code nicht gewinnen, das ist sicher. Verwendet jedoch ein paar nette Tricks mit Reichweiten. _{Und dies ist wahrscheinlich ein völliger Kauderwelsch für alle, die nicht mit PowerShell vertraut sind.}

Erläuterung

Zuerst nehmen wir Eingaben mit param($n,$k)und erwarten $k, dass es sich um ein Array handelt, z .\compute-the-multinomial-coefficient.ps1 11 @(1,4,4).

Wir beginnen mit dem Zähler (alles links von /). Das ist einfach ein Bereich 1..$n, der -joinzusammen mit berechnet *und dann mit ausgewertet wurde iex, um die Fakultät (dh 1*2*3*...*$n) zu berechnen .

Als nächstes wir Schleife über $k|%{...}und jede Iteration wir den aktuellen Wert subtrahieren $_aus $n(die wir uns nicht mehr kümmern) zu formulieren $k_mspäter. Zusätzlich generieren wir den Bereich für 1..$k_ijede Iteration, die in der Pipeline verbleibt. Diese Pipeline-Objekte werden mit dem zweiten Ausdruck, range 1..$n(der sich $k_man dieser Stelle befindet) , durch Arrays verknüpft . All dies wird schließlich -joinzusammen mit dem Zähler bearbeitet *und ausgewertet iex(dies funktioniert, da x! * y! = 1*2*3*...*x * 1*2*3*...*ywir uns nicht um die Einzelbestellung kümmern).

Schließlich /passiert das, der Zähler wird durch den Nenner geteilt und ausgegeben.

Verarbeitet die Ausgabe korrekt für größere Zahlen, da wir keine Variablen explizit als bestimmte Datentypen umwandeln, sodass PowerShell bei Bedarf automatisch die verschiedenen Datentypen umwandelt. Bei den größeren Zahlen werden die Ausgaben in wissenschaftlicher Notation ausgegeben, um die signifikanten Zahlen zu erhalten, wenn die Datentypen neu umgewandelt werden. Zum Beispiel .\compute-the-multinomial-coefficient.ps1 55 @(28)wird ausgegeben 3.82434530038022E+15. Ich bin Vermutung dies in Ordnung sein gegeben „Ausgabeformat ist ähnlich flexibel“ ist in der Herausforderung und quintopia Kommentaren angegeben „Wenn das Endergebnis in der nativ unterstützt paßt Integer - Typ, dann muss das Ergebnis genau sein. Wenn es nicht kann, da ist keine Einschränkung, was ausgegeben werden darf. "

---

Alternative

Abhängig von den Ausgabeformatierungsentscheidungen beträgt die Anzahl der Bytes 92

param($n,$k)((1..$n-join'*'|iex)/(($k|%{$n-=$_;1..$_})+(1..$n)-join'*'|iex)).ToString('G17')

Welches ist das gleiche wie oben, nur verwendet explizite Ausgabe Formatierung mit .ToString('G17')der gewünschten Anzahl von Stellen zu erreichen. Dafür 55 @(28)wird ausgegeben3824345300380220.5

---

Edit1 - Speichert 17 Bytes, indem es entfernt $dund nur direkt berechnet wird, und entfernt die Berechnung, $k_mindem es in einer Schleife $k
aneinander gereiht wird. Edit2 - Alternative Version mit expliziter Formatierung hinzugefügt

APL (Dyalog Extended) , 9 Bytes

×/2!/+\⍛,

Probieren Sie es online!

Verwenden Sie die Idee aus meiner APL-Antwort für eine andere Herausforderung, die Multinomialzahlen umfasst .

Eine implizite Funktion, deren linkes Argument die Liste von k ist und deren rechtes Argument n ist. Die Testfälle prüfen, ob sie mit Adams Lösung übereinstimmen, wobei die linken und rechten Argumente vertauscht werden.

Wie es funktioniert

×/2!/+\⍛,
     +\    ⍝ Cumulative sum of k's (up to m-1'th element)
       ⍛,  ⍝ Append n (sum of k_1 to k_m)
  2!/      ⍝ Binomial of consecutive pairs
×/         ⍝ Product

$$\frac{(k_1 + k_2 + \cdots + k_m)!}{k_1! k_2! \cdots k_m!} = \frac{(k_1 + k_2)!}{k_1! k_2!} \times \frac{(k_1 + k_2 + \cdots + k_m)!}{(k_1 + k_2)! k_3! \cdots k_m!}$$

$$= \frac{(k_1 + k_2)!}{k_1! k_2!} \times \frac{(k_1 + k_2 + k_3)!}{(k_1 + k_2)! k_3!} \times \frac{(k_1 + k_2 + \cdots + k_m)!}{(k_1 + k_2 + k_3)! \cdots k_m!}$$

$$= \cdots = \binom{k_1 + k_2}{k_1} \binom{k_1 + k_2 + k_3}{k_1 + k_2} \cdots \binom{k_1 + \cdots + k_m}{k_1 + \cdots + k_{m-1}}$$

Mathematica, 26 Bytes

#!/Times@@({#-+##2,##2}!)&

Beispiel:

In[1]:= #!/Times@@({#-+##2,##2}!)&[95,65,4,4]

Out[1]= 1934550571913396675776550070308250

Python 3, 93 91

Danke an Dennis und FryAmTheEggman .

f=lambda x:0**x or x*f(x-1)
def g(n,k):
    r=f(n)
    for i in k:r//=f(i)
    return r//f(n-sum(k))

nals ganze Zahl, kwie iterabel.

Ungolfed:

import functools #cache

@functools.lru_cache(maxsize=None) #cache results to speed up calculations
def factorial(x):
    if x <= 1: return 1
    else: return x * factorial(x-1)

def multinomial(n, k):
    ret = factorial(n)
    for i in k: ret //= factorial(i)
    km = n - sum(k)
    return ret//factorial(km)

APL (Dyalog Unicode) , 16 Byte ^SBCS

Ganz basierend auf den mathematischen Fähigkeiten meines Kollegen Marshall .

Anonyme Infix-Funktion. Nimmt k als rechtes Argument und n als linkes Argument.

{×/⍵!⍺-+\¯1↓0,⍵}

Probieren Sie es online!

{… } Anonymes Lambda; ⍺ist linkes Argument ( n ) und ⍵rechtes Argument ( k )

 0,⍵ stelle k eine Null voran

 ¯1↓ Lass den letzten Gegenstand davon fallen

 +\ kumulative Summe davon

 ⍺- subtrahiere das von n

 ⍵! ( ^k ) das

 ×/ Produkt davon

PARI / GP, 43 Bytes

Ziemlich einfach; Abgesehen von der Formatierung ist die unbenutzte Version möglicherweise identisch.

m(n,v)=n!/prod(i=1,#v,v[i]!)/(n-vecsum(v))!

Matlab 48 Bytes

Sie müssen Set formatzu longim Voraus die höhere Genauigkeit zu erhalten. Dann ist es ganz einfach:

@(n,k)factorial(n)/prod(factorial([k,n-sum(k)]))

ans(95, [65,4,4])
ans =

 1.934550571913395e+33

Pyth, 10 Bytes

/F.!MaQ-FQ

Probieren Sie es online aus: Demonstration

Erläuterung:

/F.!MaQ-FQ   implicit: Q = input list
       -FQ   reduce Q by subtraction
     aQ      append the result to Q
  .!M        compute the factorial for each number
/F           reduce by division

J, 16 Bytes

[(%*/)&:!],(-+/)

Verwendung

Bei größeren Werten wird ein Suffix von xverwendet, um Ganzzahlen mit erweiterter Genauigkeit zu kennzeichnen.

   f =: [(%*/)&:!],(-+/)
   11 f 1 4 4
34650
   15x f 5 4 3 2
37837800

Erläuterung

[(%*/)&:!],(-+/)  Input: n on LHS, A on RHS
             +/   Reduce A using addition
            -     Subtract that sum from n, this is the missing term
         ]        Get A
          ,       Append the missing term to A to make A'
[                 Get n
      &:!         Take the factorial of n and each value in A'
   */             Reduce using multiplication the factorials of A'
  %               Divide n! by that product and return

05AB1E , 8 Bytes

Ƹ«!R.«÷

Probieren Sie es online! Erläuterung:

Æ           Subtract all the elements from the first
 ¸«         Append to the original list
   !        Take the factorial of all the elements
    R.«÷    Reduce by integer division

Ich kann anscheinend keine besseren Möglichkeiten finden, um Schritt 2 oder Schritt 4 durchzuführen.

APL (Dyalog Unicode) , 17 Byte

⊢∘!÷(×/∘!⊣,⊢-1⊥⊣)

Probieren Sie es online!

Infix tacit function (Danke an @ Adám für die 2 Bytes, die es speichert.)

---

APL (Dyalog Unicode) , 19 Byte

{(!⍺)÷×/!(⍺-+/⍵),⍵}

Probieren Sie es online!

Infix Dfn.

Beide oben genannten Funktionen berechnen die angegebene Formel.

Haskell , 59-58 Bytes

f n=product[1..n]
n#k=foldl((.f).div)(f n)k`div`f(n-sum k)

Probieren Sie es online!

Danke an BMO für das Speichern von 1 Byte!

Clojure, 70 Bytes

#(let[a apply](a /(map(fn[x](a *(map inc(range x))))(conj %(a - %)))))

Erstellt eine anonyme Funktion, die alle Argumente als eine einzige Liste mit n first verwendet werden.

30 Zeichen werden "verschwendet", um die verdammte Fakultätsfunktion zu definieren. Naja.

Perl 6 ,  52  50 Bytes

->\n,\k{[*](1..n)div[*] ([*] 1..$_ for |k,[-] n,|k)}

Probier es aus

->\n,\k{[*](1..n)/[*] ([*] 1..$_ for |k,[-] n,|k)}

Teste es (Ergebnis ist ein Rational mit Nenner von 1)

Erweitert:

->     # pointy block lambda
  \n,
  \k
{
    [*]( 1 .. n )   # factorial of ｢n｣

  /                 # divide (produces Rational)

    [*]             # reduce the following using &infix:«*»

      (
          [*] 1..$_ # the factorial of

        for         # each of the following

          |k,       # the values of ｢k｣ (slipped into list)
          [-] n,|k  # ｢n｣ minus the values in ｢k｣
      )
}