Calcule el coeficiente multinomial

27

¡Es hora de otro desafío fácil en el que todos puedan participar!

El teorema multinomial establece: Fórmula para calcular la enésima potencia de un multinomio

La expresión entre paréntesis es el coeficiente multinomial, definido como:

Coeficiente multinomial

Permitir que los términos k i a la gama de más de todas las particiones de enteros de n da la n -ésima nivel de de Pascal m -simplex. Su tarea es calcular este coeficiente.

Tarea

Escriba un programa o función que tome m números, n , k 1 , k 2 , ..., k m-1 , y genere o devuelva el coeficiente multinomial correspondiente. Su programa puede tomar opcionalmente m como argumento adicional si es necesario. Tenga en cuenta que k m no está en la entrada.

  • Estos números pueden ingresarse en cualquier formato que le guste, por ejemplo, agrupados en listas o codificados en unario, o cualquier otra cosa, siempre que su código realice el cálculo real del coeficiente multinomial, y no el proceso de codificación.

  • El formato de salida es igualmente flexible.

  • Todo el código debe ejecutarse en menos de un minuto para n y m hasta 1000.

  • No te preocupes por el desbordamiento de enteros.

  • No están permitidos los elementos integrados diseñados para calcular el coeficiente multinomial.

  • Se aplican lagunas estándar.

Tanteo

Este es el código de golf: la solución más corta en bytes gana.

Casos de prueba

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
quintapia
fuente
¿Podemos tener errores de imprecisión? Es decir, en lugar de 1934550571913396675776550070308250, ¿podemos dar salida 1.9345505719133966e+33?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Si usó flotantes de 64 bits, no podrá representar la entrada [1000 {999 ones}]en absoluto, porque el exponente está mucho más allá de lo que pueden representar las flotantes de 64 bits. (Los flotantes de 128 bits probablemente serán suficientes, pero supongo que desea usar el tipo de número nativo de JavaScript?)
Martin Ender
@ MartinBüttner Sí, esa es una suposición correcta.
Conor O'Brien
2
@quintopia "¡Es hora de otro desafío fácil en el que todos puedan participar!". ¡Todos menos yo! (Como no tengo idea de qué Pascals simplex y multinomiales son D :) LOL.
Ashwin Gupta
@AshwinGupta No te preocupes por eso. ¡Simplemente calcula la expresión en la segunda imagen y listo! 👍
quintopia

Respuestas:

21

Gelatina , 7 6 bytes

;_/!:/

Mira ma, no Unicode! Este programa toma una sola lista como entrada, con n en su primer índice.

Pruébalo en línea! o verificar todos los casos de prueba a la vez .

Cómo funciona

;_/!:/ 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.
Dennis
fuente
Este es más o menos el algoritmo que tenía en mente como el más simple.
quintopia
9

CJam, 11 bytes

l~_:-+:m!:/

Ingrese como una lista única con nprimero:

[95 65 4 4]

Este asas insumos hasta ny m1000 casi al instante.

Pruébalo aquí.

Explicación

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!.
Martin Ender
fuente
Parece que realmente perderás la competencia de conteo de bytes, pero debo decir que estoy impresionado con la locura de CJam.
Phord
@phord Bueno, CJam no es rival para Jelly (o Pyth para el caso). Pero me sorprendió bastante lo compacto que terminó. Mi primera solución tenía 21 bytes, y aunque no parecía óptima, no creía que pudiera reducirla a la mitad.
Martin Ender
4

MATL , 21 15 bytes

Pongamos la función log-gamma en buen uso. Esto evita el desbordamiento interno al trabajar con logaritmos de factoriales, no con factoriales en sí.

1+ZgiO$Gs-h1+Zgs-ZeYo

Esto funciona en la versión actual (9.2.2) del lenguaje / compilador, que es anterior a este desafío.

Las entradas son: primero un número, luego un vector numérico. El resultado se produce como a double, lo que limita la salida máxima a algún lugar alrededor 2^52.

Ejemplo

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

Explicación

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
Luis Mendo
fuente
44
Pruébalo en línea! ahora tiene soporte experimental de MATL : matl.tryitonline.net/… Las sugerencias son bienvenidas.
Dennis
1
@Dennis ¡Hola! ¡¡¡Qué sorpresa!!! ¿¿Como puedo agradecerte?? Tengo una sugerencia: si alguna vez vienes a Madrid te debo una buena cena y algunas bebidas
Luis Mendo
Estoy muy agradecido Es genial tenerlo en línea. ¿Cómo manejaremos las revisiones? Todavía estoy actualizando constantemente el idioma, ya sabes ...
Luis Mendo
Por ahora, estoy actualizando manualmente los intérpretes. Si realiza una actualización, simplemente envíeme un ping en The Nineteenth Byte y lo extraeré lo antes posible. - Tendré que ir a Madrid en un futuro próximo, así que tendré en cuenta su oferta. ;)
Dennis
@Dennis ¡Genial! De esa manera podemos encontrarnos en persona!
Luis Mendo
4

PowerShell, 91 74 bytes

¡Cortejar! ¡Mi respuesta número 100 en PPCG!

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

Uf. No voy a ganar el código más corto, eso es seguro. Sin embargo, utiliza un par de buenos trucos con rangos. Y esto es probablemente una tontería completa para cualquiera que no esté familiarizado con PowerShell.

Explicación

Primero tomamos información con param($n,$k)y esperamos $kser una matriz, por ejemplo .\compute-the-multinomial-coefficient.ps1 11 @(1,4,4).

Comenzaremos con el numerador (todo a la izquierda de /). Eso es simplemente un rango desde el 1..$nque se ha -joineditado junto con *y luego evaluado iexpara calcular el factorial (es decir, 1*2*3*...*$n).

A continuación, un bucle sobre $k|%{...}y cada iteración se resta el valor actual $_de $n(que no se preocupan más) para formular $k_mmás tarde. Además, generamos el rango de 1..$k_icada iteración, que se deja en la tubería. Esos objetos de canalización se concatenan en matriz con la segunda expresión, rango 1..$n(que se encuentra $k_men este punto). Todo eso finalmente se -joinedita *y evalúa con iex, similar al numerador (esto funciona porque x! * y! = 1*2*3*...*x * 1*2*3*...*y, por lo que no nos importa el orden individual).

Finalmente, /sucede que el numerador se divide por el denominador y la salida.

Maneja la salida correctamente para números más grandes, ya que no estamos emitiendo explícitamente ninguna variable como ningún tipo de datos en particular, por lo que PowerShell volverá a emitir silenciosamente como diferentes tipos de datos sobre la marcha, según sea necesario. Para los números más grandes, salidas a través de notación científica para preservar mejor las cifras significativas a medida que los tipos de datos se vuelven a emitir. Por ejemplo, .\compute-the-multinomial-coefficient.ps1 55 @(28)saldrá 3.82434530038022E+15. Supongo que esto está bien dado que "El formato de salida es igualmente flexible" se especifica en el desafío y en los comentarios de quintopia "Si el resultado final puede caber dentro de los tipos enteros soportados de forma nativa, entonces el resultado debe ser preciso. Si no puede, hay no hay restricción sobre lo que se puede generar ".


Alternativamente

Dependiendo de las decisiones de formato de salida, lo siguiente en 92 bytes

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

Que es la misma que la anterior, simplemente usa la salida explícita formatear con .ToString('G17')para conseguir el número deseado de dígitos. Para 55 @(28)esto saldrá3824345300380220.5


Edit1: ahorró 17 bytes deshaciéndolo $dy calculándolo directamente, y deshaciéndolo del cálculo $k_mal encadenarlo mientras realizamos el bucle $k
Edit2: se agregó una versión alternativa con formato explícito

AdmBorkBork
fuente
3

APL (Dyalog Extended) , 9 bytes

×/2!/+\⍛,

Pruébalo en línea!

Usando la idea de mi respuesta APL en otro desafío que involucra a los multinomiales .

Una función tácita cuyo argumento izquierdo es la lista de k, y el argumento derecho es n. Los casos de prueba verifican si está de acuerdo con la solución de Adam con los argumentos izquierdo y derecho invertidos.

Cómo funciona

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

(k1+k2++km)!k1!k2!km!=(k1+k2)!k1!k2!×(k1+k2++km)!(k1+k2)!k3!km!

=(k1+k2)!k1!k2!×(k1+k2+k3)!(k1+k2)!k3!×(k1+k2++km)!(k1+k2+k3)!km!

==(k1+k2k1)(k1+k2+k3k1+k2)(k1++kmk1++km1)

Bubbler
fuente
2

Mathematica, 26 bytes

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

Ejemplo:

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

Out[1]= 1934550571913396675776550070308250
alephalpha
fuente
2

Pitón 3, 93 91

Gracias a Dennis y 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))

ncomo entero, kcomo iterable.

Sin 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)
Trang Oul
fuente
1
Puede usar un solo espacio en lugar de cuatro para el bit de espacio en blanco dinámico
Conor O'Brien el
Usé pestañas, fueron reemplazadas en esta publicación. El conteo de bytes parece estar bien. No estoy seguro sobre el resultado flotante y el posible desbordamiento.
Trang Oul
2
1. Esto produce un incorrecto para 95, [65, 4, 4]. Tenga en cuenta que la entrada no contiene k_m . 2. Parece que no estás usando from functools import*nada.
Dennis
2
1. Su código de golf no usa reduce. 2. import math;f=math.factorialguarda un byte. 3. Python 2 permitiría a deshacerse de la segunda /en //.
Dennis
1
Definiendo fen su propia ahorra algunos bytes : f=lambda x:0**x or x*f(x-1).
FryAmTheEggman
2

APL (Dyalog Unicode) , SBCS de 16 bytes

Completamente basado en la habilidad matemática de mi colega Marshall .

Función de infijo anónimo. Toma k como argumento derecho yn como argumento izquierdo.

{×/⍵!⍺-+10,⍵}

Pruébalo en línea!

{... } lambda anónimo; es argumento izquierdo ( n ) y argumento derecho ( k )

0,⍵ anteponer un cero a k

¯1↓ suelte el último elemento de ese

+\ suma acumulativa de eso

⍺- restar eso de n

⍵! ( k ) que

×/ producto de eso

Adán
fuente
1

PARI / GP, 43 bytes

Muy claro; Aparte del formateo, la versión sin golf podría ser idéntica.

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

Matlab 48 bytes

Debe configurarlo formatde longantemano para obtener la mayor precisión. Entonces, es bastante sencillo:

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

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

 1.934550571913395e+33
brainkz
fuente
1

Pyth, 10 bytes

/F.!MaQ-FQ

Pruébelo en línea: demostración

Explicación:

/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
Jakube
fuente
1

J, 16 bytes

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

Uso

Para valores mayores, xse usa un sufijo de para denotar enteros de precisión extendidos.

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

Explicación

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

05AB1E , 8 bytes

Ƹ«!R.«÷

Pruébalo en línea! Explicación:

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

Parece que no puedo encontrar mejores formas de realizar el paso 2 o el paso 4.

Neil
fuente
0

Clojure, 70 bytes

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

Crea una función anónima tomando todos los argumentos como una lista única, con nprimero.

Se desperdician 30 caracteres simplemente definiendo la maldita función factorial. Oh bien.

MattPutnam
fuente
0

Perl 6 ,  52  50 bytes

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

Pruébalo

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

Pruébelo (el resultado es un racional con denominador de 1)

Expandido:

->     # 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」
      )
}
Brad Gilbert b2gills
fuente