Distribusi Frekuensi Beberapa Dadu Gulungan

23

Diberikan dua bilangan bulat positif adan b, output distribusi frekuensi bergulir kali bmati sisi adan menjumlahkan hasilnya.

Distribusi frekuensi mencantumkan frekuensi setiap jumlah yang mungkin jika setiap urutan gulungan dadu yang mungkin terjadi satu kali. Jadi, frekuensinya adalah bilangan bulat yang jumlahnya sama dengan b**a.

Aturan

  • Frekuensi harus terdaftar dalam urutan jumlah yang sesuai dengan frekuensi.
  • Memberi label frekuensi dengan jumlah yang sesuai diperbolehkan, tetapi tidak diperlukan (karena jumlahnya dapat disimpulkan dari urutan yang diperlukan).
  • Anda tidak harus menangani input yang outputnya melebihi kisaran integer yang representatif untuk bahasa Anda.
  • Angka nol di depan atau di belakang tidak diizinkan. Hanya frekuensi positif yang akan muncul di output.

Uji Kasus

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
sumber
Bisakah kita berasumsi bahwa bpaling tidak 2? (Atau jika tidak, seperti apa daftar frekuensi untuk jumlah dadu 1 sisi?)
Misha Lavrov
Bisakah kita memiliki angka nol di depan atau di belakang?
xnor

Jawaban:

9

Oktaf , 38 byte

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

Cobalah online!

Penjelasan

Menambahkan variabel acak independen sesuai dengan menggabungkan fungsi massa probabilitas (PMF), atau mengalikan fungsi karakteristiknya (CF). Jadi CF dari jumlah avariabel independen, terdistribusi secara identik diberikan oleh variabel tunggal yang dinaikkan menjadi pangkat a.

CF pada dasarnya adalah transformasi Fourier dari PMF, dan dengan demikian dapat dihitung melalui FFT. PMF dari satu bdie -sided seragam pada 1, 2, ..., b. Namun, dua modifikasi diperlukan:

  • 1digunakan sebagai pengganti nilai probabilitas aktual ( 1/b). Dengan cara ini hasilnya akan dinormalisasi dan akan berisi bilangan bulat sesuai kebutuhan.
  • Padding dengan nol diperlukan sehingga output FFT memiliki ukuran yang sesuai ( a*b-a+1) dan perilaku periodik implisit yang diasumsikan oleh FFT tidak mempengaruhi hasil.

Setelah fungsi karakteristik dari jumlah telah diperoleh, FFT terbalik digunakan untuk menghitung hasil akhir, dan pembulatan diterapkan untuk mengoreksi ketidakakuratan titik-mengambang.

Contoh

Pertimbangkan input a=2, b=6. Kode a:a*b<a+bmembangun vektor dengan vektor b=6, yang berukuran nol untuk ukuran a*b-a+1:

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

Lalu fft(...)berikan

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

Seseorang hampir dapat mengenali fungsi sinc di sini (Transformasi Fourier dari pulsa persegi panjang).

(...).^amenaikkan setiap entri ke adan kemudian ifft(...)mengambil FFT terbalik, yang memberi

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

Meskipun hasil dalam kasus ini adalah bilangan bulat persis, secara umum mungkin ada kesalahan relatif dari urutan 1e-16, itulah sebabnya round(...)diperlukan.

Luis Mendo
sumber
1
Saya benar-benar terkesan!
rahnema1
@ rahnema1 Pemrosesan sinyal untuk kemenangan!
Luis Mendo
8

Mathematica, 29 byte

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

Hanya menghasilkan semua gulungan dadu yang mungkin, ambil totalnya, lalu hitung. Setiap frekuensi diberi label dengan nilainya.

Mathematica, 38 byte

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

Perluas (1+x+x^2+...+x^(a-1))^bdan ambil koefisien dari x. Karena 1+x+x^2+...+x^(a-1)fungsi pembangkit untuk satu die roll dan produk sesuai dengan konvolusi - menambah nilai dadu - hasilnya memberikan distribusi frekuensi.

Misha Lavrov
sumber
6

Haskell , 90 79 77 75 byte

Terima kasih kepada Lynn untuk trik produk Cartesian . -11 byte berkat banyak trik Haskell dari Funky Computer Man, -2 byte dari penamaan, -2 byte terima kasih kepada Laikoni. Saran bermain golf dipersilakan! Cobalah online!

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

Tidak disatukan

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
sumber
Gunakan $alih-alih ()untuk menyimpan 2 byte. TIO
Wheat Wizard
(map length$)=(length<$>)untuk dua byte
Michael Klein
4

Pyth - 10 byte

Hanya mengambil semua kombinasi dadu yang mungkin dengan mengambil produk cartesian dari [1, b], akali, menjumlahkan, dan mendapatkan panjang masing-masing kelompok penjumlahan.

lM.gksM^SE

Test Suite .

Maltysen
sumber
4

05AB1E , 8 byte

LIãO{γ€g

Cobalah online!

Bagaimana?

LIãO {γ € g - Program lengkap.

L - Rentang [1 ... masukan # 1]
 I - Input # 2.
  ã - Kekuatan Kartesius.
   O - Peta dengan jumlah.
    {- Sortir.
     γ - Kelompokkan elemen yang sama berturut-turut.
      € g - Dapatkan panjang masing-masing
Tuan Xcoder
sumber
4

R , 58 byte

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

Cobalah online!

flodel
sumber
4

R , 52 byte

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

Cobalah online!

Sebuah port dari solusi Octave @Luis Mendo , fft(z, inverse=T)sayangnya mengembalikan FFT terbalik yang tidak dinormalkan, jadi kita harus membagi panjangnya, dan mengembalikan sebuah complexvektor, jadi kita hanya mengambil bagian yang sebenarnya.

Giuseppe
sumber
dimainkan dengan baik - pengembalian untuk cmdscaleangka I kemarin :-)
flodel
@ model hah! Saya benar-benar akan memberi Anda hadiah untuk yang itu :)
Giuseppe
Anda tidak bercanda! Anda sangat dermawan! Saya senang melihat (dan belajar dari) jawaban Anda, saya akan membayarnya kembali dengan cepat!
flodel
3

SageMath, 40 byte

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

Cobalah online

convolutionmenghitung konvolusi terpisah dari dua daftar. reducemelakukan apa yang tertulis di kaleng. [1]*badalah daftar b 1s, distribusi frekuensi 1db. [[1]*b]*amembuat daftar asalinan salinan bersarang b 1.


Python 2 + NumPy , 56 byte

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

Cobalah online!

Saya sudah memasukkan solusi ini dengan yang di atas, karena mereka pada dasarnya setara. Perhatikan bahwa fungsi ini mengembalikan array NumPy dan bukan daftar Python, sehingga outputnya terlihat sedikit berbeda jika Anda printmenggunakannya.

numpy.ones((a,b))adalah cara yang "benar" untuk membuat array untuk digunakan dengan NumPy, dan karenanya dapat digunakan sebagai pengganti [[1]*b]*a, tapi sayangnya lebih lama.

Mego
sumber
3

Jelly , 5 byte

ṗS€ĠẈ

Cobalah online!

Perhatikan bahwa ini mengambil argumen dalam urutan terbalik.

Bagaimana?

ṗS € ĠL € - Program lengkap (diad) | Contoh: 6, 2

ṗ - Kekuatan Cartesian (dengan rentang implisit) | [[1, 1], [1, 2], ..., [6, 6]]
 S € - Jumlah masing-masing | [2, 3, 4, ..., 12]
   Ġ - Indeks kelompok berdasarkan nilai | [[1], [2, 7], [3, 8, 13], ..., [36]]
    L € - Panjang masing-masing grup | [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

Solusi alternatif:

ṗZSĠL€
ṗZSµLƙ
ṗS€µLƙ
Tuan Xcoder
sumber
2

Python 2 , 102 91 byte

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

Cobalah online!

ovs
sumber
2

Pari / GP , 28 byte

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

Cobalah online!

alephalpha
sumber
Sejauh yang saya tahu, ini adalah solusi terpendek yang pasti tidak kehabisan memori pada salah satu test case yang disediakan.
Misha Lavrov
1

Perl 5 , 53 byte

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

Cobalah online!

Masukkan format:

b
a
Xcali
sumber
1

JavaScript (ES6), 94 byte

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

Dibatasi oleh integer overflow 32-bit, tetapi float dapat digunakan sebagai gantinya dengan biaya 1 byte.

Neil
sumber
Umm ... ini hanya membutuhkan satu input
Herman L
@HermanLauenstein Maaf, saya entah bagaimana sepenuhnya mengabaikan bagian dari pertanyaan itu ... akan segera diperbaiki.
Neil
1

J , 25 24 21 20 byte

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

Cobalah online!

Awalnya saya menambah daftar [0..n-1] untuk mendapatkan [1..n] tetapi ternyata itu tidak perlu.

FrownyFrog
sumber
Jawaban bagus. Berikut adalah versi diam-diam untuk jumlah yang sama byte: #/.~@,@(+///)@$i.@{:. Sepertinya harus ada cara untuk mencukurnya sedikit lebih banyak membuat kata kerja diad, tetapi saya tidak bisa melakukannya.
Jonah
@Jonah Anda memiliki tambahan /di+//
FrownyFrog
Sebenarnya kamu benar. Kebetulan bekerja dengan dua arah. Saya kira solusi itu menghemat satu byte kemudian :)
Jonah
1

Javascript (ES6), 89 byte

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

Mengambil input dalam sintaks currying dalam urutan terbalik 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.
sumber
1

Sebenarnya , 13 12 byte

-1 byte terima kasih kepada Tn. Xcoder. Cobalah online!

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

Tidak disatukan

                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
sumber
Anda tidak perlu @, kan?
Tn. Xcoder
Sebagai catatan, saya menemukan alternatif yang menarik:R∙♂Σ╗╜╔⌠╜c⌡M
Tn. Xcoder
1

AWK , 191 byte

Frekuensi keluaran sebagai kolom vertikal.

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

Cobalah online!

Menambahkan 6 byte lebih memungkinkan untuk beberapa set input.

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

Cobalah online!

Robert Benson
sumber
1

Clojure, 86 byte

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

Sebuah contoh:

(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
sumber
0

C (gcc) , 142 byte

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

Cobalah online!

Biarawati Bocor
sumber
sizeof(int)? Sangat?
orlp
@orlp tergantung lingkungan, Anda tahu
Leaky Nun
2
Program C diizinkan untuk menggunakan arsitektur tertentu. Asalkan bekerja pada setidaknya satu mesin. Selanjutnya, 8akan bekerja pada arsitektur apa saja, secara keseluruhan sedikit, tapi itu tidak masalah.
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;untuk -2 byte.
Kevin Cruijssen
0

Julia , 43 byte

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

Cobalah online!

LukeS
sumber