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

23

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

Respuestas:

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

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

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

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