Distribuição de frequência de múltiplos dados

23

Dado dois números inteiros positivos ae b, bproduza a distribuição de frequência dos atempos de matriz de rolamento lateral e somando os resultados.

Uma distribuição de frequência lista a frequência de cada soma possível, se cada sequência possível de rolagem de dados ocorrer uma vez. Assim, as frequências são números inteiros cuja soma é igual b**a.

Regras

  • As frequências devem ser listadas em ordem crescente da soma à qual a frequência corresponde.
  • É permitido rotular as frequências com as somas correspondentes, mas não é obrigatório (pois as somas podem ser deduzidas da ordem necessária).
  • Você não precisa manipular entradas nas quais a saída excede o intervalo representável de números inteiros para o seu idioma.
  • Zeros à esquerda ou à direita não são permitidos. Somente frequências positivas devem aparecer na saída.

Casos de teste

Formato: a b: output

1 6: [1, 1, 1, 1, 1, 1]
2 6: [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
3 6: [1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1]
5 2: [1, 5, 10, 10, 5, 1]
6 4: [1, 6, 21, 56, 120, 216, 336, 456, 546, 580, 546, 456, 336, 216, 120, 56, 21, 6, 1]
10 10: [1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92368, 167860, 293380, 495220, 810040, 1287484, 1992925, 3010150, 4443725, 6420700, 9091270, 12628000, 17223250, 23084500, 30427375, 39466306, 50402935, 63412580, 78629320, 96130540, 115921972, 137924380, 161963065, 187761310, 214938745, 243015388, 271421810, 299515480, 326602870, 351966340, 374894389, 394713550, 410820025, 422709100, 430000450, 432457640, 430000450, 422709100, 410820025, 394713550, 374894389, 351966340, 326602870, 299515480, 271421810, 243015388, 214938745, 187761310, 161963065, 137924380, 115921972, 96130540, 78629320, 63412580, 50402935, 39466306, 30427375, 23084500, 17223250, 12628000, 9091270, 6420700, 4443725, 3010150, 1992925, 1287484, 810040, 495220, 293380, 167860, 92368, 48620, 24310, 11440, 5005, 2002, 715, 220, 55, 10, 1]
5 50: [1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465, 35960, 40920, 46376, 52360, 58905, 66045, 73815, 82251, 91390, 101270, 111930, 123410, 135751, 148995, 163185, 178365, 194580, 211876, 230300, 249900, 270725, 292825, 316246, 341030, 367215, 394835, 423920, 454496, 486585, 520205, 555370, 592090, 630371, 670215, 711620, 754580, 799085, 845121, 892670, 941710, 992215, 1044155, 1097496, 1152200, 1208225, 1265525, 1324050, 1383746, 1444555, 1506415, 1569260, 1633020, 1697621, 1762985, 1829030, 1895670, 1962815, 2030371, 2098240, 2166320, 2234505, 2302685, 2370746, 2438570, 2506035, 2573015, 2639380, 2704996, 2769725, 2833425, 2895950, 2957150, 3016881, 3075005, 3131390, 3185910, 3238445, 3288881, 3337110, 3383030, 3426545, 3467565, 3506006, 3541790, 3574845, 3605105, 3632510, 3657006, 3678545, 3697085, 3712590, 3725030, 3734381, 3740625, 3743750, 3743750, 3740625, 3734381, 3725030, 3712590, 3697085, 3678545, 3657006, 3632510, 3605105, 3574845, 3541790, 3506006, 3467565, 3426545, 3383030, 3337110, 3288881, 3238445, 3185910, 3131390, 3075005, 3016881, 2957150, 2895950, 2833425, 2769725, 2704996, 2639380, 2573015, 2506035, 2438570, 2370746, 2302685, 2234505, 2166320, 2098240, 2030371, 1962815, 1895670, 1829030, 1762985, 1697621, 1633020, 1569260, 1506415, 1444555, 1383746, 1324050, 1265525, 1208225, 1152200, 1097496, 1044155, 992215, 941710, 892670, 845121, 799085, 754580, 711620, 670215, 630371, 592090, 555370, 520205, 486585, 454496, 423920, 394835, 367215, 341030, 316246, 292825, 270725, 249900, 230300, 211876, 194580, 178365, 163185, 148995, 135751, 123410, 111930, 101270, 91390, 82251, 73815, 66045, 58905, 52360, 46376, 40920, 35960, 31465, 27405, 23751, 20475, 17550, 14950, 12650, 10626, 8855, 7315, 5985, 4845, 3876, 3060, 2380, 1820, 1365, 1001, 715, 495, 330, 210, 126, 70, 35, 15, 5, 1]
Mego
fonte
Podemos assumir que bé pelo menos 2? (Ou, se não, o que deve a lista de frequência para somas de um olhar die 1-sided como?)
Misha Lavrov
Podemos ter zeros à esquerda ou à direita?
Xnor

Respostas:

9

Oitava , 38 bytes

@(a,b)round(ifft(fft((a:a*b<a+b)).^a))

Experimente online!

Explicação

Adicionar variáveis ​​aleatórias independentes corresponde a convolver suas funções de massa de probabilidade (PMF) ou multiplicar suas funções características (CF). Assim, o CF da soma das avariáveis ​​independentes distribuídas de forma idêntica é dado pelo de uma única variável elevada ao poder de a.

O CF é essencialmente a transformada de Fourier do PMF e, portanto, pode ser calculado via FFT. A PMF de um único bdie -sided é uniforme em 1, 2, ..., b. No entanto, são necessárias duas modificações:

  • 1é usado em vez dos valores reais de probabilidade ( 1/b). Dessa forma, o resultado será desnormalizado e conterá números inteiros, conforme necessário.
  • O preenchimento com zeros é necessário para que a saída da FFT tenha o tamanho apropriado ( a*b-a+1) e o comportamento periódico implícito assumido pela FFT não afeta os resultados.

Uma vez obtida a função característica da soma, uma FFT inversa é usada para calcular o resultado final e o arredondamento é aplicado para corrigir imprecisões de ponto flutuante.

Exemplo

Considere entradas a=2, b=6. O código a:a*b<a+bcria um vetor com b=6uns, preenchidos com zero no tamanho a*b-a+1:

[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]

Então fft(...)

[36, -11.8-3.48i, 0.228+0.147i, -0.949-1.09i, 0.147+0.321i, -0.083-0.577i, -0.083+0.577i, 0.147-0.321i, -0.949+1.09i, 0.228-0.147i, -11.8+3.48i]

Quase se pode reconhecer aqui a função sinc (transformada de Fourier de um pulso retangular).

(...).^aaumenta cada entrada ae, ifft(...)em seguida, pega a FFT inversa, que fornece

[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

Embora os resultados neste caso sejam exatamente números inteiros, em geral pode haver erros relativos da ordem de 1e-16, e é por isso que round(...)é necessário.

Luis Mendo
fonte
1
Eu realmente impressionado!
rahnema1
@ rahnema1 Processamento de sinal para a vitória!
Luis Mendo
8

Mathematica, 29 bytes

Tally[Tr/@Range@#2~Tuples~#]&

Apenas gera todos os dados possíveis, pega o total e conta. Cada frequência vem rotulada com seu valor.

Mathematica, 38 bytes

CoefficientList[((x^#2-1)/(x-1))^#,x]&

Expande (1+x+x^2+...+x^(a-1))^be obtém os coeficientes de x. Como 1+x+x^2+...+x^(a-1)é a função geradora de um único rolo de matriz e os produtos correspondem a convoluções - adicionando valores de dados - o resultado fornece a distribuição de frequência.

Misha Lavrov
fonte
6

Haskell , 90 79 77 75 bytes

Obrigado a Lynn pelo truque do produto cartesiano . -11 bytes graças a muitos truques de Haskell do Funky Computer Man, -2 bytes de nomes e -2 bytes de Laikoni. Sugestões de golfe são bem-vindas! Experimente online!

import Data.List
g x=[1..x]
a!b=map length$group$sort$map sum$mapM g$b<$g a

Ungolfed

import Data.List
rangeX x = [1..x]
-- sums of all the rolls of b a-sided dice
diceRolls a b = [sum y | y <- mapM rangeX $ fmap (const b) [1..a]]
-- our dice distribution
distrib a b = [length x | x <- group(sort(diceRolls a b))]
Sherlock9
fonte
Use em $vez de ()para salvar 2 bytes. TIO
Assistente de trigo 1/1
E não usereplicate
Assistente de trigo
(map length$)=(length<$>)para dois bytes
Michael Klein
4

Pitão - 10 bytes

Apenas usa todas as combinações de dados possíveis, obtendo o produto cartesiano de [1, b], atimes, somatório e obtendo a duração de cada grupo de soma.

lM.gksM^SE

Conjunto de Teste .

Maltysen
fonte
4

05AB1E , 8 bytes

LIãO{γ€g

Experimente online!

Quão?

LIãO {γ € g - Programa completo.

L - Faixa [1 ... entrada nº 1]
 I - Entrada # 2.
  ã - Poder cartesiano.
   O - Mapa com soma.
    { - Ordenar.
     γ - Agrupe elementos iguais consecutivos.
      € g - obtenha o comprimento de cada
Mr. Xcoder
fonte
4

R , 58 bytes

function(a,b)table(rowSums(expand.grid(rep(list(1:b),a))))

Experimente online!

flodel
fonte
4

R , 52 bytes

function(a,b)Re(fft(fft(a:(a*b)<a+b)^a,T)/(a*b-a+1))

Experimente online!

Uma porta da solução Octave do @Luis Mendo , fft(z, inverse=T)infelizmente , retorna a FFT inversa não normalizada, então temos que dividir pelo comprimento, e ela retorna um complexvetor, para que tomemos apenas a parte real.

Giuseppe
fonte
bem jogado - retorno para a cmdscalefigura de ontem :-)
flodel
@flodel hah! Eu estou indo realmente para conceder-lhe uma recompensa para aquele :)
Giuseppe
Você não estava brincando! Tão generoso da sua parte! Gosto de ver (e aprender com) as suas respostas, pagarei rapidamente!
flodel
3

SageMath, 40 bytes

lambda a,b:reduce(convolution,[[1]*b]*a)

Experimente online

convolutioncalcula a convolução discreta de duas listas. reduceFaz o que diz na lata. [1]*bé uma lista de b 1s, a distribuição de frequência de 1db. [[1]*b]*afaz uma lista aninhada de acópias de b 1s.


Python 2 + NumPy , 56 bytes

lambda a,b:reduce(numpy.convolve,[[1]*b]*a)
import numpy

Experimente online!

Incluímos esta solução na acima, pois são essencialmente equivalentes. Observe que essa função retorna uma matriz NumPy e não uma lista Python; portanto, a saída parece um pouco diferente se você a printusar.

numpy.ones((a,b))é a maneira "correta" de criar uma matriz para uso com o NumPy e, portanto, pode ser usada no lugar de [[1]*b]*a, mas infelizmente é mais longa.

Mego
fonte
3

Gelatina , 5 bytes

ṗS€ĠẈ

Experimente online!

Observe que isso leva os argumentos na ordem inversa.

Quão?

ṗS € ĠL € - Programa completo (diádico) | Exemplo: 6, 2

Cart - Poder cartesiano (com alcance implícito) | [[1, 1], [1, 2], ..., [6, 6]]
 S € - soma cada | [2, 3, 4, ..., 12]
   Ġ - Agrupe índices por valores | [[1], [2, 7], [3, 8, 13], ..., [36]]
    L € - Duração de cada grupo | [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

Soluções alternativas:

ṗZSĠL€
ṗZSµLƙ
ṗS€µLƙ
Mr. Xcoder
fonte
2

Python 2 , 102 91 bytes

lambda b,a:map(map(sum,product(*[range(a)]*b)).count,range(b*~-a+1))
from itertools import*

Experimente online!

ovs
fonte
2

Pari / GP , 28 bytes

a->b->Vec(((x^b-1)/(x-1))^a)

Experimente online!

alefalpha
fonte
Até onde eu sei, essa é a solução mais curta que definitivamente não fica sem memória em nenhum dos casos de teste fornecidos.
Misha Lavrov
1

Perl 5 , 53 bytes

$g=join',',1..<>;map$r[eval]++,glob"+{$g}"x<>;say"@r"

Experimente online!

Formato de entrada:

b
a
Xcali
fonte
1

JavaScript (ES6), 94 bytes

f=(n,m,a=[1],b=[])=>n?[...Array(m)].map((_,i)=>a.map((e,j)=>b[j+=i]=(b[j]|0)+e))&&f(n-1,m,b):a
<div oninput=o.textContent=f(+n.value,+m.value).join`\n`><input id=n type=number min=0 value=0><input id=m type=number min=1 value=1><pre id=o>1

Limitado pelo estouro de número inteiro de 32 bits, mas os flutuadores podem ser usados ​​a um custo de 1 byte.

Neil
fonte
Umm ... isso leva apenas uma entrada #
Herman L
@HermanLauenstein Desculpe, de alguma forma, ignorei completamente essa parte da pergunta ... será corrigida em breve.
Neil
1

J , 25 24 21 20 bytes

3 :'#/.~,+//y$i.{:y'

Experimente online!

Inicialmente, aumentei a lista [0..n-1] para obter [1..n], mas aparentemente não é necessário.

FrownyFrog
fonte
Boa resposta. Aqui está uma versão tacitamente, mesmo número de bytes: #/.~@,@(+///)@$i.@{:. Parece que deveria haver uma maneira de reduzi-lo um pouco mais, tornando o verbo diádico, mas não consegui.
Jonah
@Jonah você tem um extra /em+//
FrownyFrog 1/17/17
Na verdade, você está certo. Acontece que funciona nos dois sentidos. Eu acho que a solução economiza um byte então :)
Jonah
1

Javascript (ES6), 89 bytes

b=>g=a=>a?(l=[..."0".repeat(b-1),...g(a-1)]).map((_,i)=>eval(l.slice(i,i+b).join`+`)):[1]

Recebe entrada na sintaxe de currying na ordem inversa f(b)(a)

f=b=>g=a=>a>0?(l=[..."0".repeat(b-1),...g(a-1)]).map((_,i)=>eval(l.slice(i,i+b).join`+`)):[1]
r=_=>{o.innerText=f(+inb.value)(+ina.value)}
<input id=ina type=number min=0 onchange="r()" value=0>
<input id=inb type=number min=1 onchange="r()" value=1>
<pre id=o></pre>

Herman L
fonte
1

Na verdade , 13 12 bytes

-1 byte graças ao Sr. Xcoder. Experimente online!

R∙♂Σ;╗╔⌠╜c⌡M

Ungolfed

                Implicit input: b, a
R∙              ath Cartesian power of [1..b]
  ♂Σ            Get all the sums of the rolls, call them dice_rolls
    ;╗          Duplicate dice_rolls and save to register 0
      ╔         Push uniquify(dice_rolls)
       ⌠  ⌡M    Map over uniquify(dice_rolls), call the variable i
        ╜         Push dice_rolls from register 0
         c        dice_rolls.count(i)
                Implict return
Sherlock9
fonte
Você não precisa do @, não é?
Xcoder 1/1
Como observação, encontrei uma alternativa interessante:R∙♂Σ╗╜╔⌠╜c⌡M
Sr. Xcoder
1

AWK , 191 bytes

Emite frequências como uma coluna vertical.

func p(z){for(m in z)S[z[m]]++
for(i=$1;i<=$1*$2;i++)print S[i]}func t(a,b,z,s){if(a){if(R++)for(n in z)for(i=0;i++<b;)s[n,i]=z[n]+i
else for(i=0;i++<b;)s[i]=i
t(--a,b,s)}else p(z)}{t($1,$2)}

Experimente online!

A adição de mais 6 bytes permite vários conjuntos de entradas.

func p(z,S){for(m in z)S[z[m]]++
for(i=$1;i<=$1*$2;i++)print S[i]}func t(a,b,z,s){if(a){if(R++)for(n in z)for(i=0;i++<b;)s[n,i]=z[n]+i
else for(i=0;i++<b;)s[i]=i
t(--a,b,s)}else p(z)}{R=0;t($1,$2)}

Experimente online!

Robert Benson
fonte
1

Clojure, 86 bytes

#(sort-by key(frequencies(reduce(fn[r i](for[y(range %2)x r](+ x y 1)))[0](range %))))

Um exemplo:

(def f #(...))
(f 5 4)

([5 1] [6 5] [7 15] [8 35] [9 65] [10 101] [11 135] [12 155] [13 155] [14 135] [15 101] [16 65] [17 35] [18 15] [19 5] [20 1])
NikoNyrh
fonte
0

C (gcc) , 142 bytes

i,j,k;int*f(a,b){int*r=malloc(sizeof(int)*(1+a*~-b));r[0]=1;for(i=1;i<=a;i++)for(j=i*~-b;j>=0;j--)for(k=1;k<b&k<=j;k++)r[j]+=r[j-k];return r;}

Experimente online!

Freira Furada
fonte
sizeof(int)? Sério?
orlp
ambiente dependente @orlp, você sabe
Leaky Nun
2
É permitido que um programa C assuma uma arquitetura específica. Contanto que funcione em pelo menos uma máquina. Além disso, 8funcionaria em qualquer arquitetura, com uma localização geral, mas tudo bem.
orlp
r[0]=1;for(i=1;i<=a;i++)for(j=i*~-b;-> for(i=r[0]=1;i<=a;)for(j=i++*~-b;para -2 bytes.
Kevin Cruijssen
0

Julia , 43 bytes

f(n,d)=reduce(conv,repmat([ones(Int,d)],n))

Experimente online!

LukeS
fonte