CODEWITHSUNDEEP
pythonrecursionfor-loopsum
Ethan Brouwer
Ethan Brouwer

Reputation: 1005

How to write this sum of a sum recursively in python?

How would I write this function: My Question (the first answer), in python recursively? This is what I have so far:

def f(n, p, k, t):
    sum(for p in xrange(1, 7):
        sum(for i in xrange(1,7):
                if n == 3: return 1
                if k == 1: return 0
                return (1/36) * f(n-1,p,k-1,t-max(p,i))
            )
        )

print sum([f(5,j,3,15) for j in xrange(1, 7)])

Any help appreciated, Thank you! :D

Edit: The question from the link is this:

"Let's say that I have 5 (n), 6-sided (d) normal dice. How would I figure out how many possible rolls there are, where the top 3 (k) numbers rolled, equal 15 (t)? How would I do this using recursion such as f(n,d,k,t)=∑i=1jf(something,with,n,d,k,t...) where the base cases are something else. How would I figure this out? Please help. Thank you."

The Answer I got was:

Going off of my comment, if we add a parameter p being the top die not in the current top k (and discard the d, because all the dice are 6-sided anyways), then I believe we get to the following: f(n,p,k,t)=∑p′=16∑i=16136⋅f(n−1,p′,k−1,t−(max(p′,i))) The variable i represents the result of next die being thrown.

I do not know if this is correct. I was just facinated with the question and wanted to have a go at it. This is what I came up with.

The final probability of sum 15 would then be ∑p=16f(5,p,3,15) with recursion base cases at n=3,k=1.

The general idea behind coming up with recursions like this is the following: You want to know the probability of reaching a state A. Then you look at all cases from which A is immedately reachable and multiply the probability of reaching those states with the probability of reaching A from that 'pre-state'. Then you sum this up over all pre-states.

The reason I did'nt copy it over, is because the sigma notations and LaTeX bits and pieces don't show up in stackoverflow.

Upvotes: 0

Views: 1914

Answers (1)

Dietrich Epp
Dietrich Epp

Reputation: 213318

You just have some of the bits mixed around.

For loops versus generator expressions

For loop:

for p in range(1, 7):
    statement()

Generator expression:

expression() for p in range(1, 7)

Note that there is no colon and the value goes before the for.

If statements versus conditional expressions

If statement:

if predicate():
    true_stmt()
else:
    false_stmt()

If expression:

true_expr() if predicate() else false_expr()

Putting it together

def f(n, p, k, t):
    return sum(sum(1 if n == 3 else
                   (0 if k == 1 else
                    (1/36) * f(n-1, p, k-1, t-max(p,i))))
                   for i in range(1, 7))
               for p in range(1, 7))

Upvotes: 1

Related Questions