473,224 Members | 1,978 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,224 software developers and data experts.

Dice probability problem

Hi,

I'm trying to find a way to calculate a distribution of
outcomes with any combination of dice. I have the basics
done, but I'm a bit unsure how to continue. My main concern
is how to make this accept any number of dice, without
having to write a new list comprehension for each case?

Here's a piece of code that shows the way I'm doing things
at the moment.

-- code begins --

# A die with n faces
D = lambda n: [x+1 for x in range(n)]

# A pool of 3 dice with 6 faces each
pool = [D(6)] * 3

# A List of all outcomes with the current 3d6 pool.
results = [x+y+z for x in pool[0] for y in pool[1]
for z in pool[2]]

# A dictionary to hold the distribution
distribution = {}

# If outcome is already a key, adds 1 to its value.
# Otherwise adds outcome to keys and sets its value
# to 1.
def count(x):
if distribution.has_key(x): distribution[x] += 1
else: distribution[x] = 1

# Maps the results with above count function.
map(count, results)

-- code ends --

Thanks,
Tomi Lindberg
Apr 4 '06 #1
11 4949
Tomi Lindberg <to*******************@pp.inet.fi.invalid> writes:
I'm trying to find a way to calculate a distribution of outcomes with any
combination of dice. I have the basics done, but I'm a bit unsure how to
continue. My main concern is how to make this accept any number of dice,
without having to write a new list comprehension for each case?


You need to think about the right way to break the problem down into some
operation that can be repeated one fewer times than there are dice (if you
just have a single dice, nothing needs to be done) and then repeat it.

An obvious candidate is adding a single dice to the sums computed so far:

def addDice(sums, dice):
return [x+y for x in dice for y in sums]

If you have less than 1 dice the answer is
# len(pool) == 1
pool[0]

After that, each time you add a dice you need to call addDice on the sum
computed for all the previous dice and the new dice:

# len(pool) == 2
addDice(resultFor1, pool[1])
addDice(pool[0], pool[1])

then

# len(pool) == 3
addDice(resultFor2, pool[2])
addDice(addDice(resultFor1, pool[1]), pool[2])
addDice(addDice(pool[0], pool[1]), pool[2])

finally you get

# len(pool) == n
addDice(addDice(addDice(..., pool[n-3]), pool[n-2]) pool[n-1])

OK, so how do we get the repetition?

Conveniently the pattern f(...f(f(x[0],x[1]),x[2])...,x[n-1]) or equivalently,
if we write the infix operator * for f: x[0]*x[1]*...*x[n-1], can just be written as
reduce(f, x) in python. So we get:

reduce(addDice, pool)
== reduce(lambda sums, dice: [x+y for x in dice for y in sums], pool)

You should presumably also try writing this out as a single function, without
using reduce (but recognizing the (left) reduction pattern is useful, even if
you don't use python's reduce).

'as
Apr 4 '06 #2
Alexander Schmolck <a.********@gmail.com> writes:
addDice(resultFor1, pool[1])
addDice(pool[0], pool[1])

sorry should have spelled out that successive lines are meant to be
equivalent, i.e.

addDice(resultFor1, pool[1])
== addDice(pool[0], pool[1])

'as
Apr 4 '06 #3
Op 2006-04-04, Tomi Lindberg schreef <to*******************@pp.inet.fi.invalid>:
Hi,

I'm trying to find a way to calculate a distribution of
outcomes with any combination of dice. I have the basics
done, but I'm a bit unsure how to continue. My main concern
is how to make this accept any number of dice, without
having to write a new list comprehension for each case?
IMO you are looking at it from the wrong side.

It would be better to construct distributions for one
die and make a function that can 'add' two distributions
together. So for 3D6 you first add the distribution of
a D6 to the distribution of a D6 and to this result
you add the distribution of a D6 again.

If you need more to start, just ask.
Here's a piece of code that shows the way I'm doing things
at the moment.

-- code begins --

# A die with n faces
D = lambda n: [x+1 for x in range(n)]

# A pool of 3 dice with 6 faces each
pool = [D(6)] * 3

# A List of all outcomes with the current 3d6 pool.
results = [x+y+z for x in pool[0] for y in pool[1]
for z in pool[2]]


This is very inefficient. I wouldn't want to calculate
the distribution of 10D10 this way.

Try to think how you would do this with only D2's.

(Triangle of Pascal) and generalize it.

--
Antoon Pardon
Apr 4 '06 #4
First, thanks to Antoon and Alexander for replying.

Antoon Pardon wrote:
It would be better to construct distributions for one
die and make a function that can 'add' two distributions
together.


As both replies pointed to this direction, I tried to take
that route. Here's the unpolished code I came up with. Does
it look even remotely sane way to accomplish my goal?

-- code begins --

# A die with n faces
D = lambda n: [x+1 for x in range(n)]

# A new die with 6 faces
d6 = D(6)

# Adds another die to results.
def add_dice(sums, die):
# If first die, all values appear once
if not sums:
for face in die:
sums[face] = 1
# Calculating the number of appearances for additional
# dice
else:
new_sums = {}
for k in sums.keys():
for f in die:
if new_sums.has_key(k+f):
new_sums[k+f] += sums[k]
else:
new_sums[k+f] = sums[k]
sums = new_sums
return sums

sums = add_dice({}, d6)
sums = add_dice(sums, d6)
sums = add_dice(sums, d6)

-- code ends --

Thanks,
Tomi Lindberg
Apr 4 '06 #5

Tomi Lindberg wrote:

# A die with n faces
D = lambda n: [x+1 for x in range(n)]


That can be written:

D = lambda n : range(1,n+1)

Gerard

Apr 4 '06 #6
That looks reasonable. The operation you are implementing is known as
'convolution' and is equivalent to multiplying polynomials. It would be
a little more general if you had the input 'die' be a sequence of the
count for each outcome, so d6 would be [1]*6 (or [0]+[1]*6 if you
prefer). That would allow allow you to represent unfair dice and also
to add not just a die to a distribution, but to add any two
distributions, so you can play tricks like computing 16d6 as
(d6)*2*2*2*2. (The code above is a convolution that restricts the
second distribution 'die' to have only 0 and 1 coefficients.) The
general convolution can be implemented much like what you have, except
that you need another multiplication (to account for the fact that the
coefficient is not always 0 or 1). My not particularly efficient
implementation:

def vsum(seq1, seq2):
return [ a + b for a, b in zip(seq1, seq2) ]

def vmul(s, seq):
return [ s * a for a in seq ]

# Convolve 2 sequences
# equivalent to adding 2 probabililty distributions
def conv(seq1, seq2):
n = (len(seq1) + len(seq2) -1)
ans = [ 0 ] * n
for i, v in enumerate(seq2):
vec = [ 0 ] * i + vmul(v, seq1) + [ 0 ] * (n - i - len(seq1))
ans = vsum(ans, vec)
return ans

# Convolve a sequence n times with itself
# equivalent to multiplying distribution by n
def nconv(n, seq):
ans = seq
for i in range(n-1):
ans = conv(ans, seq)
return ans

print nconv(3, [ 1 ] * 6)
print nconv(3, [ 1.0/6 ] * 6)
print nconv(2, [ .5, .3, .2 ])

[1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1]
[0.0046296296296296294, 0.013888888888888888, 0.027777777777777776,
0.046296296296296294, 0.069444444444444448, 0.097222222222222238,
0.11574074074074074, 0.125, 0.125, 0.11574074074074073,
0.097222222222222224, 0.069444444444444448, 0.046296296296296294,
0.027777777777777776, 0.013888888888888888, 0.0046296296296296294]
[0.25, 0.29999999999999999, 0.29000000000000004, 0.12,
0.040000000000000008]

Apr 4 '06 #7
Op 2006-04-04, Tomi Lindberg schreef <to*******************@pp.inet.fi.invalid>:
First, thanks to Antoon and Alexander for replying.

Antoon Pardon wrote:
It would be better to construct distributions for one
die and make a function that can 'add' two distributions
together.
As both replies pointed to this direction, I tried to take
that route. Here's the unpolished code I came up with. Does
it look even remotely sane way to accomplish my goal?

-- code begins --

# A die with n faces
D = lambda n: [x+1 for x in range(n)]

# A new die with 6 faces
d6 = D(6)

# Adds another die to results.
def add_dice(sums, die):
# If first die, all values appear once
if not sums:
for face in die:
sums[face] = 1
# Calculating the number of appearances for additional
# dice
else:
new_sums = {}
for k in sums.keys():
for f in die:
if new_sums.has_key(k+f):
new_sums[k+f] += sums[k]
else:
new_sums[k+f] = sums[k]
sums = new_sums
return sums

sums = add_dice({}, d6)
sums = add_dice(sums, d6)
sums = add_dice(sums, d6)

-- code ends --


IMO you are making things too complicated and not general
enough. Here is my proposal.

-----

import operator

class Distribution(dict):

'''A distribution is a dictionary where the keys are dice
totals and the values are the number of possible ways
this total can come up '''

def __add__(self, term):

'''Take two distributions and combine them into one.'''

result = Distribution()
for k1, v1 in self.iteritems():
for k2, v2 in term.iteritems():
k3 = k1 + k2
v3 = v1 * v2
try:
result[k3] += v3
except KeyError:
result[k3] = v3
return result

def __rmul__(self, num):
tp = num * [self]
return reduce(operator.add, tp)

def D(n):

''' One die has a distribution where each result has
one possible way of coming up '''
return Distribution((i,1) for i in xrange(1,n+1))
sum3d6 = 3 * D(6)
sum2d6p2d4 = 2 * D(6) + 2 * D(4)

-----

--
Antoon Pardon
Apr 5 '06 #8
Antoon Pardon wrote:
IMO you are making things too complicated and not general
enough.


I believe that the above is very likely more than just your
opinion :) Programming is just an occasional hobby to me,
and I lack both experience and deeper (possibly a good chunk
of shallow as well) knowledge on the subject. I'll study the
code you posted, and make further questions if something
remains unclear afterwards.

Thanks,
Tomi Lindberg
Apr 5 '06 #9
Tomi Lindberg <to*******************@pp.inet.fi.invalid> writes:
# Adds another die to results.
def add_dice(sums, die):
# If first die, all values appear once
I'd add something like

sums = sums or {}

because otherwise your function will sometimes mutate sums and sometimes
return a fresh object, which usually is a very bad thing as it can easily lead
to quite nasty bugs.
if not sums:
for face in die:
sums[face] = 1
# Calculating the number of appearances for additional
# dice
else:
new_sums = {}
for k in sums.keys():
for f in die:
if new_sums.has_key(k+f):
new_sums[k+f] += sums[k]
else:
new_sums[k+f] = sums[k]
sums = new_sums
return sums


'as
Apr 5 '06 #10
Antoon Pardon wrote:
def __rmul__(self, num):
tp = num * [self]
return reduce(operator.add, tp)

sum3d6 = 3 * D(6)


One basic question: is there any particular reason not to
use __mul__ instead (that would allow me to use both 3 *
D(6) and D(6) * 3, while __rmul__ raises an AttributeError
with the latter)? Difference between the two methods is
slightly unclear to me.

Thanks,
Tomi Lindberg
Apr 5 '06 #11
On 2006-04-05, Tomi Lindberg <to*******************@pp.inet.fi.invalid> wrote:
Antoon Pardon wrote:
def __rmul__(self, num):
tp = num * [self]
return reduce(operator.add, tp)

sum3d6 = 3 * D(6)
One basic question: is there any particular reason not to
use __mul__ instead (that would allow me to use both 3 *
D(6) and D(6) * 3, while __rmul__ raises an AttributeError
with the latter)?


Well 3 * D(6) is similar to the notation used in roleplaying,
while D(6) * 3 would make me think of the distribution
{3:1, 6:1, 9:1, 12:1, 15:1, 18:}
Difference between the two methods is
slightly unclear to me.


I have to look it up myself regularly. But in this case
it was more a matter of some intuition that 3 * D(6)
was not the same as D(6) * 3. You may have a different
intuition.

--
Antoon Pardon
Apr 6 '06 #12

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
by: Elliot Temple | last post by:
Problem: Randomly generate 10 integers from 0-100 inclusive, and sum them. Do that twice. What is the probability the two sums are 390 apart? I have code to do part of it (below), and I know how...
17
by: Jose Durazo | last post by:
Hello, I'm doing an exercise to simulate rolling a pair of dice 36,000 times, then count and display how many times the simulation rolls each possible sum. For some reason each time I run my...
1
by: clairelee0322 | last post by:
I am a c++ beginner and i am working on a dice loop lab. This program should roll two dice (each dice is from 1 to 6) and then total them together. The user should be able to input how many times...
0
by: veera ravala | last post by:
ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
0
by: mar23 | last post by:
Here's the situation. I have a form called frmDiceInventory with subform called subfrmDice. The subform's control source is linked to a query called qryDiceInventory. I've been trying to pick up the...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.