Czas na kolejne łatwe wyzwanie, w którym wszyscy mogą wziąć udział!

Twierdzenie o wielomianach stwierdza:

Wyrażenie w nawiasach to współczynnik wielomianowy, zdefiniowany jako:

Dopuszczenie, aby terminy k _i obejmowały wszystkie partycje całkowite n, daje n -ty poziom m -simplex Pascala. Twoim zadaniem jest obliczenie tego współczynnika.

Zadanie

Napisz program lub funkcję, która pobierze m liczb, n , k ₁ , k ₂ , ..., k _m-1 , i wyświetli lub zwróci odpowiedni współczynnik wielomianowy. Twój program może opcjonalnie wziąć m jako dodatkowy argument, jeśli zajdzie taka potrzeba. Zauważ, że k _m nie znajduje się na wejściu.

• Liczby te mogą być wprowadzane w dowolnym formacie, który nam się podoba, na przykład pogrupowane w listy lub zakodowane jako jednoargumentowe lub cokolwiek innego, o ile kod oblicza rzeczywiste obliczenie współczynnika wielomianowego, a nie proces kodowania.

• Format wyjściowy jest podobnie elastyczny.

• Cały kod powinien działać w ciągu mniej niż jednej minuty n i m do 1000.

• Nie przejmuj się przepełnieniem liczb całkowitych.

• Wbudowane funkcje obliczania współczynnika wielomianowego są niedozwolone.

• Obowiązują standardowe luki.

Punktacja

To jest kod golfowy: wygrywa najkrótsze rozwiązanie w bajtach.

Przypadki testowe

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

Galaretka , 7 6 bajtów

;_/!:/

Spójrz, nie ma Unicode! Ten program przyjmuje pojedynczą listę jako dane wejściowe, gdzie n ma swój pierwszy indeks.

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe jednocześnie .

Jak to działa

;_/!:/ 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 bajtów

l~_:-+:m!:/

Wprowadź jako pojedynczą listę z npierwszym:

[95 65 4 4]

To obsługuje dane wejściowe do 1000 ni mprawie natychmiast.

Sprawdź to tutaj.

Wyjaśnienie

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 bajtów

Postawmy funkcję log-gamma do dobrego wykorzystania. Pozwala to uniknąć wewnętrznego przepełnienia poprzez pracę z logarytmami silni, a nie z samymi silnikami.

1+ZgiO$Gs-h1+Zgs-ZeYo

Działa to w bieżącej wersji (9.2.2) języka / kompilatora, która jest wcześniejsza niż to wyzwanie.

Wejściami są: najpierw liczba, a następnie wektor numeryczny. Wynik jest wytwarzany jako a double, co ogranicza maksymalną moc wyjściową do około 2^52.

Przykład

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

Wyjaśnienie

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 bajtów

_{Zabiegać! Moja setna odpowiedź na PPCG!}

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

Uff Na pewno nie wygrasz najkrótszego kodu. Wykorzystuje kilka schludnych sztuczek z zasięgami. _{I jest to prawdopodobnie kompletny bełkot dla każdego, kto nie zna PowerShell.}

Wyjaśnienie

Najpierw bierzemy dane wejściowe param($n,$k)i oczekujemy, $kże będziemy tablicą, np .\compute-the-multinomial-coefficient.ps1 11 @(1,4,4).

Zaczniemy od licznika (wszystko po lewej stronie /). Jest to po prostu zakres od 1..$ntego, który został -joinedytowany razem, *a następnie oceniany za pomocą iexdo obliczenia silni (tj 1*2*3*...*$n.).

Następnie, pętla nad $k|%{...}i każda iteracja odejmujemy aktualną wartość $_z $n(które już nie obchodzi o) formułowanie $k_mpóźniej. Dodatkowo generujemy zakres 1..$k_ikażdej iteracji, który zostaje w potoku. Te obiekty potoku zostają połączone w tablicę z drugim wyrażeniem - zakresem 1..$n(który jest $k_mw tym momencie). Wszystko to jest ostatecznie -joinedytowane razem *i oceniane za pomocą iex, podobnie jak licznik (działa to x! * y! = 1*2*3*...*x * 1*2*3*...*y, ponieważ nie dbamy o indywidualne zamawianie).

Wreszcie, /zdarza się, licznik jest dzielony przez mianownik i dane wyjściowe.

Obsługuje dane wyjściowe poprawnie dla większych liczb, ponieważ nie przesyłamy jawnie żadnych zmiennych jako poszczególnych typów danych, więc PowerShell po cichu przerzuci w razie potrzeby różne typy danych w locie. W przypadku większych liczb dane wyjściowe za pomocą notacji naukowej mają najlepiej zachować znaczące liczby w miarę ponownego przesyłania typów danych. Na przykład .\compute-the-multinomial-coefficient.ps1 55 @(28)wyświetli 3.82434530038022E+15. Zakładam, że jest to OK, biorąc pod uwagę, że „Format wyjściowy jest podobnie elastyczny” jest określony w komentarzach i komentarzach kwintopii „Jeśli końcowy wynik może mieścić się w natywnie obsługiwanych typach liczb całkowitych, wynik musi być dokładny. Jeśli nie, nie ma ograniczeń co do wyniku. ”

---

Alternatywnie

W zależności od decyzji o formatowaniu danych wyjściowych następujące po 92 bajtach

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

Który jest taki sam jak powyżej, po prostu używa jawnego formatowania wyjściowego za pomocą, .ToString('G17')aby osiągnąć pożądaną liczbę cyfr. Do 55 @(28)tego wyjdzie3824345300380220.5

---

Edycja1 - Zapisano 17 bajtów, pozbywając się $di obliczając bezpośrednio, a pozbywając się obliczeń $k_m, ciągnąc je podczas pętli $k
Edytuj2 - Dodano alternatywną wersję z jawnym formatowaniem

APL (Dyalog Extended) , 9 bajtów

×/2!/+\⍛,

Wypróbuj online!

Wykorzystując pomysł z mojej odpowiedzi APL na inne wyzwanie, które dotyczy wielomianów .

Milcząca funkcja, której lewy argument jest listą k, a prawy argument to n. Przypadki testowe sprawdzają, czy zgadzają się z rozwiązaniem Adama, z odrzuconymi lewymi i prawymi argumentami.

Jak to działa

×/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 bajtów

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

Przykład:

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

Out[1]= 1934550571913396675776550070308250

Python 3, 93 91

Dzięki Dennis i 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))

njako liczba całkowita, kjak iterowalna.

Nie golfowany:

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 bajtów ^SBCS

Całkowicie oparty na matematycznych umiejętnościach mojego kolegi Marshalla .

Anonimowa funkcja poprawki. Przyjmuje k jako prawy argument, a n jako lewy argument.

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

Wypróbuj online!

{… } Anonimowa lambda; ⍺jest lewym argumentem ( n ) i ⍵jest prawym argumentem ( k )

 0,⍵ dodaj zero do k

 ¯1↓ upuść z tego ostatni element

 +\ łączna suma tego

 ⍺- odejmij to od n

 ⍵! ( ^k ) to

 ×/ produkt tego

PARI / GP, 43 bajty

Całkiem proste; oprócz formatowania wersja bez golfa może być identyczna.

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

Matlab 48 bajtów

Trzeba ustawić format, aby longz wyprzedzeniem, aby uzyskać większą precyzję. Zatem jest to całkiem proste:

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

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

 1.934550571913395e+33

Pyth, 10 bajtów

/F.!MaQ-FQ

Wypróbuj online: demonstracja

Wyjaśnienie:

/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 bajtów

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

Stosowanie

W przypadku większych wartości sufiks xjest używany do oznaczania liczb całkowitych o rozszerzonej precyzji.

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

Wyjaśnienie

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

Ƹ«!R.«÷

Wypróbuj online! Wyjaśnienie:

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

Nie mogę znaleźć lepszych sposobów wykonania kroku 2 lub 4.

APL (Dyalog Unicode) , 17 bajtów

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

Wypróbuj online!

Infix milcząca funkcja (dzięki @ Adám za 2 bajty, które zapisuje.)

---

APL (Dyalog Unicode) , 19 bajtów

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

Wypróbuj online!

Infix Dfn.

Obie powyższe funkcje obliczają podaną formułę.

Haskell , 59 58 bajtów

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

Wypróbuj online!

Dzięki BMO za uratowanie 1 bajtu!

Clojure, 70 bajtów

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

Tworzy anonimową funkcję, biorąc wszystkie argumenty jako jedną listę, z npierwszym.

30 znaków jest „zmarnowanych”, co definiuje cholerną funkcję silni. No cóż.

Perl 6 ,  52  50 bajtów

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

Sprawdź to

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

Przetestuj (wynik jest wymierny o mianowniku 1)

Rozszerzony:

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