Saatnya untuk tantangan mudah lainnya di mana semua dapat berpartisipasi!

Teorema multinomial menyatakan:

Ekspresi dalam tanda kurung adalah koefisien multinomial, didefinisikan sebagai:

Mengizinkan istilah k _i untuk menjangkau semua partisi integer dari n memberikan level ke- n dari m -simplex Pascal . Tugas Anda adalah menghitung koefisien ini.

Tugas

Tulis program atau fungsi yang mengambil angka m , n , k ₁ , k ₂ , ..., k _m-1 , dan menghasilkan atau mengembalikan koefisien multinomial yang sesuai. Program Anda secara opsional dapat menganggap m sebagai argumen tambahan jika perlu. Perhatikan bahwa k _m tidak ada dalam input.

• Angka-angka ini dapat dimasukkan dalam format apa pun yang disukai, misalnya dikelompokkan ke dalam daftar atau disandikan di unary, atau apa pun, selama perhitungan aktual dari koefisien multinomial dilakukan oleh kode Anda, dan bukan proses pengkodean.

• Format output juga fleksibel.

• Semua kode harus berjalan dalam waktu kurang dari satu menit untuk n dan m hingga 1000.

• Jangan khawatir tentang integer overflow.

• Built-in yang dirancang untuk menghitung koefisien multinomial tidak diperbolehkan.

• Celah standar berlaku.

Mencetak gol

Ini adalah kode golf: Solusi terpendek dalam byte yang menang.

Uji kasus

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

Jelly , 7 6 byte

;_/!:/

Lihat bu, tidak ada Unicode! Program ini mengambil satu daftar sebagai input, dengan n pada indeks pertamanya.

Cobalah online! atau verifikasi semua kasus uji sekaligus .

Bagaimana itu bekerja

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

l~_:-+:m!:/

Masukan sebagai daftar tunggal dengan yang npertama:

[95 65 4 4]

Ini menangani input hingga ndan m1000 cukup banyak secara instan.

Uji di sini.

Penjelasan

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 byte

Mari kita gunakan fungsi log-gamma dengan baik. Ini menghindari internal yang meluap dengan bekerja dengan logaritma faktorial, bukan dengan faktorial itu sendiri.

1+ZgiO$Gs-h1+Zgs-ZeYo

Ini berfungsi dalam versi saat ini (9.2.2) dari bahasa / kompiler, yang lebih awal dari tantangan ini.

Inputnya adalah: pertama angka, lalu vektor numerik. Hasilnya diproduksi sebagai double, yang membatasi output maksimum di suatu tempat di sekitar 2^52.

Contoh

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

Penjelasan

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 byte

_{Merayu! Jawaban ke-100 saya di PPCG!}

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

Wah. Tidak akan memenangkan kode terpendek, itu sudah pasti. Namun, gunakan beberapa trik yang rapi dengan rentang. _{Dan ini mungkin omong kosong lengkap bagi siapa pun yang tidak terbiasa dengan PowerShell.}

Penjelasan

Pertama kita mengambil input dengan param($n,$k)dan berharap $kmenjadi array, mis .\compute-the-multinomial-coefficient.ps1 11 @(1,4,4).

Kami akan mulai dengan pembilang (semuanya di sebelah kiri /). Itu hanya rentang dari 1..$nyang telah -joindisatukan dengan *dan kemudian dievaluasi dengan iexuntuk menghitung faktorial (yaitu, 1*2*3*...*$n).

Selanjutnya, kita mengulang $k|%{...}dan setiap iterasi kita kurangi nilai saat ini $_dari $n(yang kita tidak peduli lagi) untuk dirumuskan $k_mnanti. Selain itu, kami menghasilkan rentang 1..$k_isetiap iterasi, yang tersisa di jalur pipa. Objek-objek pipa mendapatkan array-concatenated dengan ekspresi kedua, range 1..$n(yang $k_mpada titik ini). Semua itu akhirnya -joindiedit bersama *dan dievaluasi dengan iex, mirip dengan pembilang (ini berfungsi karena x! * y! = 1*2*3*...*x * 1*2*3*...*y, jadi kami tidak peduli tentang pemesanan individu).

Akhirnya, yang /terjadi, pembilang dibagi dengan penyebut, dan keluaran.

Menangani keluaran dengan benar untuk angka yang lebih besar, karena kami tidak secara eksplisit menampilkan variabel apa pun sebagai tipe data tertentu, sehingga PowerShell akan secara diam-diam menampilkan kembali tipe data yang berbeda saat diperlukan. Untuk angka yang lebih besar, keluaran melalui notasi ilmiah untuk mempertahankan angka-angka penting dengan baik ketika datatypes kembali dicetak. Sebagai contoh, .\compute-the-multinomial-coefficient.ps1 55 @(28)akan menampilkan 3.82434530038022E+15. Saya menganggap ini OK karena "Format output juga fleksibel" ditentukan dalam tantangan dan komentar quintopia "Jika hasil akhir dapat masuk dalam tipe bilangan bulat yang didukung secara native, maka hasilnya harus akurat. Jika tidak bisa, ada tidak ada batasan pada apa yang mungkin menjadi output. "

---

kalau tidak

Bergantung pada keputusan pemformatan output, berikut pada 92 byte

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

Yang sama seperti di atas, hanya menggunakan format output eksplisit dengan .ToString('G17')untuk mencapai jumlah digit yang diinginkan. Untuk 55 @(28)ini akan menampilkan3824345300380220.5

---

Sunting1 - Disimpan 17 byte dengan menyingkirkan $ddan hanya menghitungnya secara langsung, dan menyingkirkan perhitungan untuk $k_mdengan merangkai bersama sementara kita mengulangi $k
Edit2 - Menambahkan versi alternatif dengan pemformatan eksplisit

APL (Dyalog Extended) , 9 byte

×/2!/+\⍛,

Cobalah online!

Menggunakan ide dari APL saya menjawab pada tantangan lain yang melibatkan multinomial .

Fungsi diam-diam yang argumen kiri adalah daftar k, dan argumen kanan adalah n. Kasus uji memeriksa apakah itu setuju dengan solusi Adam dengan argumen kiri dan kanan terbalik.

Bagaimana itu bekerja

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

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

Contoh:

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

Out[1]= 1934550571913396675776550070308250

Python 3, 93 91

Terima kasih untuk Dennis dan 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))

nsebagai integer, kseperti iterable.

Tidak Disatukan:

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

Seluruhnya didasarkan pada keterampilan matematika rekan saya Marshall .

Fungsi infiks anonim. Membawa k sebagai argumen kanan dan n sebagai argumen kiri.

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

Cobalah online!

{... } lambda anonim; ⍺adalah argumen kiri ( n ) dan ⍵argumen benar ( k )

 0,⍵ tambahkan nol ke k

 ¯1↓ jatuhkan item terakhir dari itu

 +\ jumlah kumulatif itu

 ⍺- kurangi dari n

 ⍵! ( ^k ) itu

 ×/ produk itu

PARI / GP, 43 byte

Cukup mudah; selain dari pemformatan, versi yang tidak serigala mungkin identik.

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

Matlab 48 byte

Anda perlu set formatuntuk longdi muka untuk mendapatkan presisi yang lebih tinggi. Kemudian, cukup mudah:

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

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

 1.934550571913395e+33

Pyth, 10 byte

/F.!MaQ-FQ

Cobalah online: Demonstrasi

Penjelasan:

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

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

Pemakaian

Untuk nilai yang lebih besar, sufiks xdigunakan untuk menunjukkan bilangan bulat presisi yang diperluas.

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

Penjelasan

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

Ƹ«!R.«÷

Cobalah online! Penjelasan:

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

Saya sepertinya tidak bisa menemukan cara yang lebih baik untuk melakukan langkah 2 atau langkah 4.

APL (Dyalog Unicode) , 17 byte

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

Cobalah online!

Fungsi infix diam-diam (Terima kasih kepada @ Adám untuk 2 byte yang dihematnya.)

---

APL (Dyalog Unicode) , 19 byte

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

Cobalah online!

Infix Dfn.

Kedua fungsi di atas menghitung rumus yang diberikan.

Haskell , 59 58 byte

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

Cobalah online!

Terima kasih kepada BMO untuk menghemat 1 byte!

Clojure, 70 byte

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

Membuat fungsi anonim dengan mengambil semua argumen sebagai satu daftar, dengan yang npertama.

30 karakter "terbuang" hanya mendefinisikan fungsi faktorial. Baiklah.

Perl 6 ,  52  50 byte

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

Menguji

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

Mengujinya (hasilnya adalah Rasional dengan penyebut 1)

Diperluas:

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