Distribution de fréquence de plusieurs lancers de dés

23

Étant donné deux nombres entiers positifs aet b, affichez la distribution de fréquence des temps de bdé roulage sur une face aet résumez les résultats.

Une distribution de fréquence répertorie la fréquence de chaque somme possible si chaque séquence possible de lancers de dés se produit une fois. Ainsi, les fréquences sont des entiers dont la somme est égale b**a.

Règles

  • Les fréquences doivent être répertoriées dans l'ordre croissant de la somme à laquelle la fréquence correspond.
  • L'étiquetage des fréquences avec les sommes correspondantes est autorisé, mais pas obligatoire (puisque les sommes peuvent être déduites de l'ordre requis).
  • Vous n'avez pas à gérer les entrées lorsque la sortie dépasse la plage représentable d'entiers pour votre langue.
  • Les zéros au début ou à la fin ne sont pas autorisés. Seules les fréquences positives doivent apparaître dans la sortie.

Cas de test

Format: 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
la source
Pouvons-nous supposer que bc'est au moins 2? (Ou sinon, à quoi devrait ressembler la liste des fréquences pour les sommes d'un dé unilatéral?)
Misha Lavrov
Pouvons-nous avoir des zéros de début ou de fin?
xnor

Réponses:

9

Octave , 38 octets

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

Essayez-le en ligne!

Explication

L'ajout de variables aléatoires indépendantes correspond à la convolution de leurs fonctions de masse de probabilité (PMF) ou à la multiplication de leurs fonctions caractéristiques (CF). Ainsi, le CF de la somme des avariables indépendantes et distribuées de manière identique est donné par celui d'une seule variable élevée à la puissance dea .

Le CF est essentiellement la transformée de Fourier de la PMF, et peut donc être calculé via une FFT. Le PMF d'un seul bdie est uniforme à flancs 1, 2..., b. Cependant, deux modifications sont nécessaires:

  • 1 est utilisé à la place des valeurs de probabilité réelles (1/b ). De cette façon, le résultat sera dénormalisé et contiendra des entiers selon les besoins.
  • Un remplissage avec des zéros est nécessaire pour que la sortie FFT ait la taille appropriée ( a*b-a+1) et que le comportement périodique implicite supposé par la FFT n'affecte pas les résultats.

Une fois la fonction caractéristique de la somme obtenue, une FFT inverse est utilisée pour calculer le résultat final et un arrondi est appliqué pour corriger les inexactitudes en virgule flottante.

Exemple

Tenez compte des entrées a=2, b=6. Le code a:a*b<a+bconstruit un vecteur avec des b=6uns, complété à la taille zéro a*b-a+1:

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

fft(...)Donne ensuite

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

On peut presque reconnaître ici la fonction sinc (transformée de Fourier d'une impulsion rectangulaire).

(...).^aélève chaque entrée aet ifft(...)prend ensuite la FFT inverse, ce qui donne

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

Bien que les résultats dans ce cas soient exactement des nombres entiers, en général, il peut y avoir des erreurs relatives de l'ordre de 1e-16, c'est pourquoi il round(...)est nécessaire.

Luis Mendo
la source
1
J'ai vraiment impressionné!
rahnema1
@ rahnema1 Traitement du signal pour la victoire!
Luis Mendo
8

Mathematica, 29 octets

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

Génère simplement tous les lancers de dés possibles, prend leurs totaux, puis compte. Chaque fréquence est étiquetée avec sa valeur.

Mathematica, 38 octets

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

Développe (1+x+x^2+...+x^(a-1))^bet prend les coefficients de x. Puisque 1+x+x^2+...+x^(a-1)c'est la fonction de génération pour un seul jet de dé et que les produits correspondent à des circonvolutions - en ajoutant des valeurs de dés - le résultat donne la distribution de fréquence.

Misha Lavrov
la source
6

Haskell , 90 79 77 75 octets

Merci à Lynn pour l' astuce produit cartésienne . -11 octets grâce à de nombreuses astuces Haskell de Funky Computer Man, -2 octets de nommage, -2 octets grâce à Laikoni. Les suggestions de golf sont les bienvenues! Essayez-le en ligne!

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

Non 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
la source
Utilisez $au lieu de ()pour enregistrer 2 octets. TIO
Wheat Wizard
(map length$)=(length<$>)pour deux octets
Michael Klein
4

Pyth - 10 octets

Prend simplement toutes les combinaisons de dés possibles en prenant le produit cartésien de [1, b], les atemps, la somme et la longueur de chaque groupe de somme.

lM.gksM^SE

Suite de tests .

Maltysen
la source
4

05AB1E , 8 octets

LIãO{γ€g

Essayez-le en ligne!

Comment?

LIãO {γ € g - Programme complet.

L - Plage [1 ... entrée # 1]
 I - Entrée # 2.
  ã - Puissance cartésienne.
   O - Carte avec somme.
    { - Trier.
     γ - Regroupe les éléments égaux consécutifs.
      € g - Obtenez la longueur de chacun
M. Xcoder
la source
4

R , 58 octets

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

Essayez-le en ligne!

flodel
la source
4

R , 52 octets

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

Essayez-le en ligne!

Un portage de la solution Octave de @Luis Mendo , fft(z, inverse=T)renvoie malheureusement la FFT inverse non normalisée, nous devons donc diviser par la longueur, et elle renvoie un complexvecteur, nous ne prenons donc que la partie réelle.

Giuseppe
la source
bien joué - retour sur investissement pour la cmdscalefigure d' hier :-)
flodel
@flodel hah! En fait, je vais vous accorder une prime pour celui-là :)
Giuseppe
Tu ne plaisantais pas! Si généreux de votre part! J'aime voir (et apprendre de) vos réponses, je les rembourserai rapidement!
flodel
3

SageMath, 40 octets

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

Essayez-le en ligne

convolutioncalcule la convolution discrète de deux listes. reducefait ce qu'il dit sur l'étain. [1]*best une liste de b 1s, la distribution de fréquence de 1db. [[1]*b]*afait une liste imbriquée de acopies de l' b 1art.


Python 2 + NumPy , 56 octets

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

Essayez-le en ligne!

J'ai inclus cette solution avec celle ci-dessus, car elles sont essentiellement équivalentes. Notez que cette fonction renvoie un tableau NumPy et non une liste Python, donc la sortie semble un peu différente si vous printle faites .

numpy.ones((a,b))est la façon "correcte" de créer un tableau à utiliser avec NumPy, et donc il pourrait être utilisé à la place de [[1]*b]*a, mais c'est malheureusement plus long.

Mego
la source
3

Gelée , 5 octets

ṗS€ĠẈ

Essayez-le en ligne!

Notez que cela prend les arguments dans l'ordre inverse.

Comment?

ṗS € ĠL € - Programme complet (dyadique) | Exemple: 6, 2

ṗ - Puissance cartésienne (avec plage implicite) | [[1, 1], [1, 2], ..., [6, 6]]
 S € - somme chacun | [2, 3, 4, ..., 12]
   Ġ - Indices de groupe par valeurs | [[1], [2, 7], [3, 8, 13], ..., [36]]
    L € - Longueur de chaque groupe | [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

Solutions alternatives:

ṗZSĠL€
ṗZSµLƙ
ṗS€µLƙ
M. Xcoder
la source
2

Python 2 , 102 91 octets

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

Essayez-le en ligne!

ovs
la source
2

Pari / GP , 28 octets

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

Essayez-le en ligne!

alephalpha
la source
Pour autant que je sache, il s'agit de la solution la plus courte qui ne manque certainement pas de mémoire sur l'un des cas de test fournis.
Misha Lavrov
1

Perl 5 , 53 octets

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

Essayez-le en ligne!

Format d'entrée:

b
a
Xcali
la source
1

JavaScript (ES6), 94 octets

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

Limité par un débordement d'entier de 32 bits, mais des flottants pourraient être utilisés à la place au coût de 1 octet.

Neil
la source
Umm ... cela ne prend qu'une seule entrée
Herman L
@HermanLauenstein Désolé, j'ai en quelque sorte complètement ignoré cette partie de la question ... corrigera sous peu.
Neil
1

J , 25 24 21 20 octets

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

Essayez-le en ligne!

Initialement, j'ai incrémenté la liste [0..n-1] pour obtenir [1..n] mais apparemment, ce n'est pas nécessaire.

FrownyFrog
la source
Bonne réponse. Voici une version tacite du même nombre d'octets: #/.~@,@(+///)@$i.@{:. Il semble qu'il devrait y avoir un moyen de le raser un peu plus, rendant le verbe dyadique, mais je n'ai pas pu le faire.
Jonah
@Jonah vous avez un supplément /en+//
FrownyFrog
En fait, tu as raison. Il se trouve que cela fonctionne dans les deux sens. Je suppose que cette solution permet d'économiser un octet alors :)
Jonah
1

Javascript (ES6), 89 octets

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

Prend l'entrée dans la syntaxe de curry dans l'ordre inverse 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
la source
1

Réellement , 13 12 octets

-1 octet merci à M. Xcoder. Essayez-le en ligne!

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

Non 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
la source
Vous n'en avez pas besoin @, n'est- ce pas?
M. Xcoder, du
En guise de note, j'ai trouvé une alternative intéressante:R∙♂Σ╗╜╔⌠╜c⌡M
M. Xcoder
1

AWK , 191 octets

Émet les fréquences sous forme de colonne verticale.

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

Essayez-le en ligne!

L'ajout de 6 octets supplémentaires permet plusieurs ensembles d'entrées.

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

Essayez-le en ligne!

Robert Benson
la source
1

Clojure, 86 octets

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

Un exemple:

(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
la source
0

C (gcc) , 142 octets

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

Essayez-le en ligne!

Leaky Nun
la source
sizeof(int)? Vraiment?
orlp
@orlp dépendant de l'environnement, vous savez
Leaky Nun
2
Il est permis à un programme C d'assumer une architecture particulière. Tant qu'il fonctionne sur au moins une machine. De plus, 8cela fonctionnerait sur n'importe quelle architecture, surutilisant un peu, mais ça va.
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;pour -2 octets.
Kevin Cruijssen