Dados dos enteros positivos ay b, bgenera la distribución de frecuencia de los atiempos de un dado rodando y sumando los resultados.

Una distribución de frecuencia enumera la frecuencia de cada suma posible si cada secuencia posible de tiradas de dados ocurre una vez. Por lo tanto, las frecuencias son enteros cuya suma es igual b**a.

Reglas

Las frecuencias deben enumerarse en orden creciente de la suma a la que corresponde la frecuencia.
Se permite etiquetar las frecuencias con las sumas correspondientes, pero no es obligatorio (ya que las sumas se pueden inferir del orden requerido).
No tiene que manejar entradas donde la salida excede el rango representable de enteros para su idioma.
Los ceros iniciales o finales no están permitidos. Solo deben aparecer frecuencias positivas en la salida.

Casos de prueba

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]

code-golf integer probability-theory statistics Mego
fuente

¿Podemos suponer que bes al menos 2? (O si no, ¿cómo debería ser la lista de frecuencias para las sumas de un dado de 1 cara?)

Misha Lavrov,

¿Podemos tener ceros iniciales o finales?

xnor

9

Octava , 38 bytes

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

Pruébalo en línea!

Explicación

Agregar variables aleatorias independientes corresponde a convolucionar sus funciones de masa de probabilidad (PMF), o multiplicar sus funciones características (CF). Por lo tanto, la CF de la suma de avariables independientes, distribuidas idénticamente, está dada por la de una sola variable elevada a la potencia dea .

La CF es esencialmente la transformada de Fourier de la PMF y, por lo tanto, se puede calcular a través de una FFT. El PMF de un solo btroquel -sided es uniforme en 1, 2, ..., b. Sin embargo, se requieren dos modificaciones:

1se usa en lugar de los valores de probabilidad reales ( 1/b). De esta forma, el resultado se desnormalizará y contendrá enteros según sea necesario.
Se necesita relleno con ceros para que la salida FFT tenga el tamaño apropiado ( a*b-a+1) y el comportamiento periódico implícito asumido por la FFT no afecta los resultados.

Una vez que se ha obtenido la función característica de la suma, se utiliza una FFT inversa para calcular el resultado final, y se aplica el redondeo para corregir las imprecisiones de punto flotante.

Ejemplo

Considere insumos a=2, b=6. El código a:a*b<a+bcrea un vector con b=6unos, rellenado con ceros a medida a*b-a+1:

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

Luego fft(...)da

[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]

Aquí casi se puede reconocer la función sinc (transformada de Fourier de un pulso rectangular).

(...).^alevanta cada entrada ay luego ifft(...)toma la FFT inversa, que da

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

Aunque los resultados en este caso son exactamente enteros, en general puede haber errores relativos del orden de 1e-16, por lo que round(...)es necesario.

Luis Mendo
fuente

1

Realmente me impresionó!

rahnema1

@ rahnema1 ¡Procesamiento de señales para la victoria!

Luis Mendo

8

Mathematica, 29 bytes

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

Solo genera todas las tiradas de dados posibles, toma sus totales, luego cuenta. Cada frecuencia viene etiquetada con su valor.

Mathematica, 38 bytes

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

Expande (1+x+x^2+...+x^(a-1))^by toma los coeficientes de x. Dado que 1+x+x^2+...+x^(a-1)es la función generadora de un solo dado y los productos corresponden a convoluciones (sumando valores de dados), el resultado proporciona la distribución de frecuencias.

Misha Lavrov
fuente

6

Haskell , 90 79 77 75 bytes

Gracias a Lynn por el truco del producto cartesiano . -11 bytes gracias a muchos trucos de Haskell de Funky Computer Man, -2 bytes de nombres, -2 bytes gracias a Laikoni. Sugerencias de golf son bienvenidas! Pruébalo en línea!

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

Sin golf

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
fuente

Use en $lugar de ()para guardar 2 bytes. TIO

Wheat Wizard

Y no usereplicate

Wheat Wizard

Y use mapas en lugar de comprensiones

Wheat Wizard

También puede predefinir su lambda

Wheat Wizard

(map length$)=(length<$>)por dos bytes

Michael Klein

4

Pyth - 10 bytes

Simplemente toma todas las combinaciones posibles de dados tomando el producto cartesiano de [1, b], atiempos, sumando y obteniendo la longitud de cada grupo de suma.

lM.gksM^SE

Test Suite .

Maltysen
fuente

4

05AB1E , 8 bytes

LIãO{γ€g

Pruébalo en línea!

¿Cómo?

LIãO {γ € g - Programa completo.

L - Rango [1 ... entrada # 1]
 I - Entrada # 2.
  ã - Poder cartesiano.
   O - Mapa con suma.
    {- Ordenar.
     γ - Agrupa elementos iguales consecutivos.
      € g - Obtenga la longitud de cada

Sr. Xcoder
fuente

4

R , 58 bytes

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

Pruébalo en línea!

flodel
fuente

4

R , 52 bytes

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

Pruébalo en línea!

Un puerto de la solución Octave de @Luis Mendo , fft(z, inverse=T)desafortunadamente , devuelve la FFT inversa no normalizada, por lo que tenemos que dividir por la longitud, y devuelve un complexvector, por lo que tomamos solo la parte real.

Giuseppe
fuente

bien jugado - recuperación de la inversión de ayer cmdscaleme imagino :-)

flodel

@flodel hah! De hecho, voy a otorgarle una recompensa por eso :)

Giuseppe

No estabas bromeando! ¡Tan generoso de tu parte! Disfruto viendo (y aprendiendo) sus respuestas, ¡lo devolveré rápidamente!

flodel

3

SageMath, 40 bytes

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

Pruébalo en línea

convolutioncalcula la convolución discreta de dos listas. reduceHace lo que dice en la lata. [1]*bes una lista de b 1s, la distribución de frecuencias de 1db. [[1]*b]*ahace una lista anidada de acopias de b 1s.

Python 2 + NumPy , 56 bytes

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

Pruébalo en línea!

He incluido esta solución con la anterior, ya que son esencialmente equivalentes. Tenga en cuenta que esta función devuelve una matriz NumPy y no una lista de Python, por lo que la salida se ve un poco diferente si lo printhace.

numpy.ones((a,b))es la forma "correcta" de hacer una matriz para usar con NumPy y, por lo tanto, podría usarse en lugar de [[1]*b]*a, pero desafortunadamente es más larga.

Mego
fuente

3

Jalea , 5 bytes

ṗS€ĠẈ

Pruébalo en línea!

Tenga en cuenta que esto toma los argumentos en orden inverso.

¿Cómo?

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

ṗ - Poder cartesiano (con rango implícito) | [[1, 1], [1, 2], ..., [6, 6]]
 S € - Suma cada uno | [2, 3, 4, ..., 12]
   Ġ - Agrupar índices por valores | [[1], [2, 7], [3, 8, 13], ..., [36]]
    L € - Longitud de cada grupo | [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

Soluciones alternativas:

ṗZSĠL€
ṗZSµLƙ
ṗS€µLƙ

Sr. Xcoder
fuente

2

Python 2 , 102 91 bytes

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

Pruébalo en línea!

ovs
fuente

2

Haskell , 61 bytes

g x=[1..x]
a#b=[sum[1|m<-mapM g$b<$g a,sum m==n]|n<-[a..a*b]]

Pruébalo en línea! Usar como a#b.

En parte basado en la respuesta Haskell de Sherlock9 .

Laikoni
fuente

2

MATL , 9 bytes

:Z^!Xs8#u

El mismo enfoque que la respuesta Pyth de Maltysen .

Las entradas están en orden inverso. Pruébalo en línea!

Luis Mendo
fuente

2

Pari / GP , 28 bytes

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

Pruébalo en línea!

alephalpha
fuente

Por lo que puedo decir, esta es la solución más corta que definitivamente no se queda sin memoria en ninguno de los casos de prueba proporcionados.

Misha Lavrov

1

Perl 5 , 53 bytes

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

Pruébalo en línea!

Formato de entrada:

b
a

Xcali
fuente

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

Expandir fragmento

Limitado por un desbordamiento de enteros de 32 bits, pero en su lugar se podrían usar flotantes a un costo de 1 byte.

Neil
fuente

Umm ... esto solo requiere una entrada

Herman L

@HermanLauenstein Lo siento, de alguna manera pasé por alto esa parte de la pregunta ... se solucionará en breve.

Neil

1

J , 25 24 21 20 bytes

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

Pruébalo en línea!

Inicialmente incrementé la lista [0..n-1] para obtener [1..n] pero aparentemente no es necesario.

FrownyFrog
fuente

Buena respuesta. Aquí hay una versión tácita por el mismo número de bytes: #/.~@,@(+///)@$i.@{:. Parece que debería haber una manera de reducirlo un poco más haciendo que el verbo sea diádico, pero no pude hacerlo.

Jonás

@Jonah tienes un extra /en+//

FrownyFrog

En realidad, tienes razón. Simplemente sucede que funciona en ambos sentidos. Supongo que esa solución ahorra un byte entonces :)

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]

Toma la entrada en la sintaxis curry en orden inverso 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>

Expandir fragmento

Herman L
fuente

1

En realidad , 13 12 bytes

-1 byte gracias al Sr. Xcoder. Pruébalo en línea!

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

Sin golf

                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
fuente

No necesitas el @, ¿verdad?

Sr. Xcoder

Como nota al margen, encontré una alternativa interesante:R∙♂Σ╗╜╔⌠╜c⌡M

Sr. Xcoder

1

AWK , 191 bytes

Emite frecuencias como una columna 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)}

Pruébalo en línea!

Agregar 6 bytes más permite múltiples 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)}

Pruébalo en línea!

Robert Benson
fuente

1

Clojure, 86 bytes

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

Un ejemplo:

(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
fuente

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;}

Pruébalo en línea!

Monja permeable
fuente

sizeof(int)? De Verdad?

orlp

@orlp depende del entorno, ya sabes

Leaky Nun

2

Está permitido que un programa C asuma una arquitectura particular. Siempre que funcione en al menos una máquina. Además, 8funcionaría en cualquier arquitectura, sobreasignando un poco, pero está bien.

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))

Pruébalo en línea!

Lucas
fuente

Distribución de frecuencia de múltiples rollos de dados

Reglas

Casos de prueba

Respuestas:

Octava , 38 bytes

Explicación

Ejemplo

Mathematica, 29 bytes

Mathematica, 38 bytes

Haskell , 90 79 77 75 bytes

Pyth - 10 bytes

05AB1E , 8 bytes

¿Cómo?

R , 58 bytes

R , 52 bytes

SageMath, 40 bytes

Python 2 + NumPy , 56 bytes

Jalea , 5 bytes

¿Cómo?

Python 2 , 102 91 bytes

Haskell , 61 bytes

MATL , 9 bytes

Pari / GP , 28 bytes

Perl 5 , 53 bytes

JavaScript (ES6), 94 bytes

J , 25 24 21 20 bytes

Javascript (ES6), 89 bytes

En realidad , 13 12 bytes

AWK , 191 bytes

Clojure, 86 bytes

C (gcc) , 142 bytes

Julia , 43 bytes