Calcular o coeficiente multinomial

27

Hora de outro desafio fácil, no qual todos podem participar!

O teorema multinomial afirma: Fórmula para calcular a enésima potência de um multinomial

A expressão entre parênteses é o coeficiente multinomial, definido como:

Coeficiente multinomial

Permitindo que os termos de k i a variar ao longo de todas as partições inteiros de n dá o n -simo nível de de Pascal m -simplex. Sua tarefa é calcular esse coeficiente.

Tarefa

Escreva um programa ou função que pegue m números, n , k 1 , k 2 , ..., k m-1 e produz ou retorne o coeficiente multinomial correspondente. Seu programa pode opcionalmente considerar m como argumento adicional, se necessário. Observe que k m não está na entrada.

  • Esses números podem ser inseridos em qualquer formato que você queira, por exemplo, agrupado em listas ou codificado em unário ou qualquer outra coisa, desde que a computação real do coeficiente multinomial seja realizada pelo seu código, e não pelo processo de codificação.

  • O formato de saída é igualmente flexível.

  • Todo o código deve ser executado em menos de um minuto para n e m até 1000.

  • Não se preocupe com o excesso de números inteiros.

  • Built-ins projetados para calcular o coeficiente multinomial não são permitidos.

  • Aplicam-se brechas padrão.

Pontuação

Este é o código golf: A solução mais curta em bytes vence.

Casos de teste

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
quintopia
fonte
Podemos ter erros de imprecisão? Ou seja, em vez de 1934550571913396675776550070308250, podemos produzir 1.9345505719133966e+33?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Se você usou flutuadores de 64 bits, não poderá representar nenhuma entrada [1000 {999 ones}], porque o expoente está muito além do que os flutuadores de 64 bits podem representar. (Bóias de 128 bits provavelmente será suficiente, mas eu estou supondo que você quer usar tipo de número nativo do JavaScript?)
Martin Ender
@ MartinBüttner Sim, essa é uma suposição correta.
Conor O'Brien
2
@quintopia "Hora de outro desafio fácil, no qual todos podem participar!". Todos menos eu! (Desde que eu não tenho idéia do que Pascals simplex e multinomiais são D :) LOL.
Ashwin Gupta
@AshwinGupta Não se preocupe. Você acabou de calcular a expressão na segunda imagem e pronto! Quint
quintopia

Respostas:

21

Geléia , 7 6 bytes

;_/!:/

Olha ma, não Unicode! Este programa usa uma única lista como entrada, com n em seu primeiro índice.

Experimente online! ou verifique todos os casos de teste de uma só vez .

Como 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
fonte
Esse é o algoritmo que eu tinha em mente como sendo o mais simples.
quintopia 14/01
9

CJam, 11 bytes

l~_:-+:m!:/

Insira como uma única lista com o nprimeiro:

[95 65 4 4]

Este alças entradas até ne m1000 praticamente instantaneamente.

Teste aqui.

Explicação

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
fonte
Parece que você realmente perderá a competição de contagem de bytes, mas devo dizer que estou impressionado com a insanidade de CJam.
phord
@phord Bem, CJam não é páreo para Jelly (ou Pyth). Mas fiquei bastante surpreso com o quão compacto acabou. Minha primeira solução tinha 21 bytes e, embora não parecesse ideal, não achei que pudesse cortar isso pela metade.
Martin Ender
4

MATL , 21 15 bytes

Vamos usar bem a função log-gama . Isso evita o transbordamento interno ao trabalhar com logaritmos de fatoriais, não com os próprios fatoriais.

1+ZgiO$Gs-h1+Zgs-ZeYo

Isso funciona na versão atual (9.2.2) do idioma / compilador, anterior a esse desafio.

As entradas são: primeiro um número, depois um vetor numérico. O resultado é produzido como a double, o que limita a produção máxima para algo em torno de2^52 .

Exemplo

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

Explicação

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
fonte
4
Experimente online! agora tem suporte experimental a MATL: matl.tryitonline.net/… Sugestões são bem-vindas.
Dennis
1
@Dennis Hey! Que surpresa!!! Como posso agradecer ?? Eu tenho uma sugestão: se você alguma vez vir a Madrid Devo-lhe um bom jantar e algumas bebidas
Luis Mendo
Estou muito agradecido. É ótimo tê-lo online. Como vamos lidar com as revisões? Ainda estou constantemente atualizando o idioma, você sabe ...
Luis Mendo 14/01
Por enquanto, estou atualizando manualmente os intérpretes. Se você fizer uma atualização, basta me enviar um ping no The XIX XIX Byte e eu puxarei o mais rápido possível. - Terei que ir a Madri em um futuro próximo, por isso vou manter sua oferta em mente. ;)
Dennis
@Dennis Great! Dessa forma, podemos nos encontrar pessoalmente!
Luis Mendo
4

PowerShell, 91 74 bytes

Uau! Minha 100ª resposta sobre PPCG!

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

Ufa. Não vai ganhar código mais curto, isso é certo. Usa alguns truques legais com intervalos, no entanto. E isso provavelmente é uma bobagem completa para quem não conhece o PowerShell.

Explicação

Primeiro, aceitamos param($n,$k)e esperamos $kser uma matriz, por exemplo .\compute-the-multinomial-coefficient.ps1 11 @(1,4,4).

Começaremos com o numerador (tudo à esquerda de /). Isso é simplesmente um intervalo 1..$nque foi -joineditado *e avaliado com iexpara calcular o fatorial (ou seja,1*2*3*...*$n ).

Em seguida, vamos varrer $k|%{...}e cada iteração que subtrair o valor atual $_da $n(que não se preocupam mais) para formular $k_mmais tarde. Além disso, geramos o intervalo a 1..$k_icada iteração, que fica no pipeline. Esses objetos de pipeline são concatenados com a segunda expressão, range 1..$n(que está $k_mneste momento). Tudo isso é finalmente -joineditado *e avaliado com iex, semelhante ao numerador (isso funciona porquex! * y! = 1*2*3*...*x * 1*2*3*...*y , portanto, não nos importamos com pedidos individuais).

finalmente, o / acontece é que o numerador é dividido pelo denominador e pela saída.

Lida com a saída corretamente para números maiores, já que não estamos expressamente convertendo nenhuma variável como qualquer tipo de dados específico, portanto, o PowerShell silenciosamente reproduz novamente diferentes tipos de dados em tempo real, conforme necessário. Para os números maiores, as saídas via notação científica preservam melhor os números significativos à medida que os tipos de dados são relançados. Por exemplo, .\compute-the-multinomial-coefficient.ps1 55 @(28)será exibido 3.82434530038022E+15. Estou presumindo que isso esteja correto, dado que "O formato de saída é similarmente flexível" está especificado no desafio e nos comentários da quintopia "Se o resultado final puder caber nos tipos inteiros suportados nativamente, o resultado deverá ser preciso. Se não puder, não há restrição sobre o que pode ser produzido ".


alternativamente

Dependendo das decisões de formatação da saída, o seguinte em 92 bytes

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

Que é o mesmo que o acima, apenas usa formatação de saída explícita com .ToString('G17')para alcançar o número desejado de dígitos. Para 55 @(28)isso irá produzir3824345300380220.5


Edit1 - Economizou 17 bytes, livrando-se $de calculando-o diretamente, e livrando-se do cálculo $k_mamarrando-o enquanto fazemos o loop $k
Edit2 - Adicionada versão alternativa com formatação explícita

AdmBorkBork
fonte
3

APL (Dyalog Extended) , 9 bytes

×/2!/+\⍛,

Experimente online!

Usando a ideia da minha resposta APL em outro desafio que envolve multinomiais .

Uma função tácita cujo argumento à esquerda é a lista de k e o argumento à direita é n. Os casos de teste verificam se concorda com a solução de Adam com os argumentos esquerdo e direito invertidos.

Como 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
fonte
2

Mathematica, 26 bytes

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

Exemplo:

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

Out[1]= 1934550571913396675776550070308250
alefalpha
fonte
2

Python 3, 93 91

Agradecimentos a Dennis e 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))

n como inteiro, k como iterável.

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)
Trang Oul
fonte
1
Você pode usar um único espaço, em vez de quatro para a dinâmica espaço em branco mordeu
Conor O'Brien
Eu usei abas, elas foram substituídas neste post. A contagem de bytes parece estar correta. Não tenho certeza sobre o resultado da flutuação e o possível estouro.
Trang Oul
2
1. Isso produz um incorreto para 95, [65, 4, 4]. Observe que a entrada não contém k_m . 2. Você parece não estar usando from functools import*nada.
Dennis
2
1. Seu código de golfe não usa reduce. 2. import math;f=math.factorialsalva um byte. 3. Python 2 permitiria que você a se livrar do segundo /no //.
Dennis
1
Definindo fem seu próprio salva alguns bytes : f=lambda x:0**x or x*f(x-1).
FryAmTheEggman
2

APL (Dyalog Unicode) , 16 bytes SBCS

Totalmente baseado nas habilidades matemáticas do meu colega Marshall .

Função de infixo anônimo. Toma k como argumento certo e n como argumento esquerdo.

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

Experimente online!

{... } lambda anônima; é argumento à esquerda ( n ) e é argumento à direita ( k )

0,⍵ acrescente um zero a k

¯1↓ largar o último item desse

+\ soma acumulada disso

⍺- subtrair isso de n

⍵! ( k ) que

×/ produto disso

Adão
fonte
1

PARI / GP, 43 bytes

Bem direto; além da formatação, a versão não-gasta pode muito bem ser idêntica.

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

Matlab 48 bytes

Você precisa definir formatcom longantecedência para obter a maior precisão. Então, é bem direto:

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

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

 1.934550571913395e+33
brainkz
fonte
1

Pitão, 10 bytes

/F.!MaQ-FQ

Experimente online: Demonstração

Explicação:

/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
fonte
1

J, 16 bytes

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

Uso

Para valores maiores, um sufixo de xé usado para indicar números inteiros de precisão estendidos.

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

Explicação

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

05AB1E , 8 bytes

Ƹ«!R.«÷

Experimente online! Explicação:

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

Não consigo encontrar melhores maneiras de executar as etapas 2 ou 4.

Neil
fonte
0

Clojure, 70 bytes

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

Cria uma função anônima, recebendo todos os argumentos como uma única lista, com n primeiro.

30 caracteres são "desperdiçados" apenas definindo a função fatorial. Ah bem.

MattPutnam
fonte
0

Perl 6 ,  52  50 bytes

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

Teste-o

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

Teste (o resultado é um Rational com denominador 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
fonte