Il est temps pour un autre défi facile auquel tous peuvent participer!

Le théorème multinomial énonce:

L'expression entre parenthèses est le coefficient multinomial, défini comme:

Laisser les termes k _i s'étendre sur toutes les partitions entières de n donne le n -ième niveau du m- simplex de Pascal . Votre tâche consiste à calculer ce coefficient.

Tâche

Écrivez un programme ou une fonction qui prend m nombres, n , k ₁ , k ₂ , ..., k _m-1 , et génère ou renvoie le coefficient multinomial correspondant. Votre programme peut éventuellement prendre m comme argument supplémentaire si nécessaire. Notez que k _m n'est pas en entrée.

• Ces nombres peuvent être entrés dans n'importe quel format souhaité, par exemple regroupés dans des listes ou codés en unaire, ou toute autre chose, tant que le calcul réel du coefficient multinomial est effectué par votre code, et non par le processus de codage.

• Le format de sortie est également flexible.

• Tout le code doit s'exécuter en moins d'une minute pour n et m jusqu'à 1000.

• Ne vous inquiétez pas du débordement d'entier.

• Les éléments intégrés conçus pour calculer le coefficient multinomial ne sont pas autorisés.

• Des échappatoires standard s'appliquent.

Notation

Voici le code golf: la solution la plus courte en octets gagne.

Cas de test

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

Gelée , 7 6 octets

;_/!:/

Regardez ma, pas d'Unicode! Ce programme prend une seule liste en entrée, avec n à son premier index.

Essayez-le en ligne! ou vérifiez tous les cas de test à la fois .

Comment ça marche

;_/!:/ 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 octets

l~_:-+:m!:/

Entrez comme une seule liste avec d' nabord:

[95 65 4 4]

Cela gère les entrées jusqu'à net m1000 à peu près instantanément.

Testez-le ici.

Explication

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 octets

Mettons à profit la fonction log-gamma . Cela évite les débordements internes en travaillant avec les logarithmes des factorielles, pas avec les factorielles elles-mêmes.

1+ZgiO$Gs-h1+Zgs-ZeYo

Cela fonctionne dans la version actuelle (9.2.2) du langage / compilateur, qui est antérieure à ce défi.

Les entrées sont: d'abord un nombre, puis un vecteur numérique. Le résultat est produit en tant que double, ce qui limite la sortie maximale à quelque part 2^52.

Exemple

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

Explication

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 74 octets

_{Courtiser! Ma 100ème réponse sur PPCG!}

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

Ouf. Ne va pas gagner le code le plus court, c'est sûr. Utilise cependant quelques astuces soignées avec des plages. _{Et c'est probablement du charabia complet pour quiconque ne connaît pas PowerShell.}

Explication

Nous prenons d'abord une entrée avec param($n,$k)et nous nous attendons $kà être un tableau, par exemple .\compute-the-multinomial-coefficient.ps1 11 @(1,4,4).

Nous allons commencer par le numérateur (tout à gauche de /). Il s'agit simplement d'une plage à partir de 1..$nlaquelle a été -joinéditée avec *, puis évaluée avec iexpour calculer la factorielle (c.-à 1*2*3*...*$n-d.).

Ensuite, on boucle sur $k|%{...}et chaque itération on retranche la valeur actuelle $_de $n(que nous ne se soucient pas plus) de formuler $k_mplus tard. De plus, nous générons la plage à 1..$k_ichaque itération, qui reste sur le pipeline. Ces objets de pipeline sont concaténés en tableau avec la deuxième expression, range 1..$n(qui est $k_mà ce stade). Tout cela est finalement -joinédité avec *et évalué avec iex, similaire au numérateur (cela fonctionne parce que x! * y! = 1*2*3*...*x * 1*2*3*...*y, donc nous ne nous soucions pas de la commande individuelle).

Enfin, /cela arrive, le numérateur est divisé par le dénominateur et la sortie.

Les poignées sortent correctement pour des nombres plus importants, car nous ne convertissons pas explicitement de variables en tant que types de données particuliers, donc PowerShell sera automatiquement rediffusé en tant que types de données différents à la volée selon les besoins. Pour les plus grands nombres, les sorties via la notation scientifique permettent de conserver au mieux les chiffres significatifs lors de la refonte des types de données. Par exemple, .\compute-the-multinomial-coefficient.ps1 55 @(28)sortira 3.82434530038022E+15. Je suppose que cela est OK étant donné que "Le format de sortie est tout aussi flexible" est spécifié dans les commentaires du défi et de la quintopie "Si le résultat final peut tenir dans les types entiers pris en charge nativement, alors le résultat doit être précis. S'il ne le peut pas, il n'est pas une restriction sur ce qui peut être sorti. "

---

Alternativement

Selon les décisions de formatage de sortie, ce qui suit à 92 octets

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

Ce qui est le même que ci-dessus, utilise simplement un formatage de sortie explicite avec .ToString('G17')pour atteindre le nombre de chiffres souhaité. Car 55 @(28)cela produira3824345300380220.5

---

Edit1 - Enregistré 17 octets en se débarrassant $det en le calculant directement, et en se débarrassant du calcul $k_men le $k
cordant pendant que nous bouclons Edit2 - Ajout d'une version alternative avec un formatage explicite

APL (Dyalog Extended) , 9 octets

×/2!/+\⍛,

Essayez-le en ligne!

Utiliser l'idée de ma réponse APL sur un autre défi qui implique des multinomiaux .

Fonction tacite dont l'argument de gauche est la liste des k et l'argument de droite est n. Les cas de test vérifient si elle est d'accord avec la solution d' Adam avec les arguments gauche et droit inversés.

Comment ça marche

×/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 octets

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

Exemple:

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

Out[1]= 1934550571913396675776550070308250

Python 3, 93 91

Merci à Dennis et 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))

ncomme entier, kcomme itérable.

Non golfé:

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 octets ^SBCS

Entièrement basé sur les compétences mathématiques de mon collègue Marshall .

Fonction d'infixation anonyme. Prend k comme argument de droite et n comme argument de gauche.

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

Essayez-le en ligne!

{… } Lambda anonyme; ⍺est l'argument gauche ( n ) et l' ⍵argument droit ( k )

 0,⍵ ajouter un zéro à k

 ¯1↓ déposez le dernier élément de cette

 +\ somme cumulée de cette

 ⍺- soustrayez cela de n

 ⍵! ( ^k ) que

 ×/ produit de cela

PARI / GP, 43 octets

Assez simple; à part le formatage, la version non golfée pourrait bien être identique.

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

Matlab 48 octets

Vous devez régler formatà l' longavance pour obtenir une précision plus élevée. Ensuite, c'est assez simple:

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

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

 1.934550571913395e+33

Pyth, 10 octets

/F.!MaQ-FQ

Essayez-le en ligne: Démonstration

Explication:

/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 octets

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

Usage

Pour les valeurs plus grandes, un suffixe de xest utilisé pour désigner les entiers à précision étendue.

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

Explication

[(%*/)&:!],(-+/)  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 octets

Ƹ«!R.«÷

Essayez-le en ligne! Explication:

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

Je n'arrive pas à trouver de meilleures façons d'effectuer l'étape 2 ou l'étape 4.

APL (Dyalog Unicode) , 17 octets

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

Essayez-le en ligne!

Infix tacit function (Merci à @ Adám pour les 2 octets qu'il enregistre.)

---

APL (Dyalog Unicode) , 19 octets

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

Essayez-le en ligne!

Infix Dfn.

Les deux fonctions ci-dessus calculent la formule donnée.

Haskell , 59 58 octets

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

Essayez-le en ligne!

Merci à BMO d' avoir économisé 1 octet!

Clojure, 70 octets

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

Crée une fonction anonyme prenant tous les arguments en une seule liste, avec nfirst.

30 caractères sont "gaspillés" juste pour définir la putain de fonction factorielle. Tant pis.

Perl 6 ,  52  50 octets

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

Essaye-le

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

Testez-le (le résultat est un rationnel avec un dénominateur de 1)

Étendu:

->     # 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｣
      )
}