How can I use a recursive loop to find the amount of times a value shows up between rolling any amount of dice with any amount of sides?

Question

I am trying to write a function that prints out a dictionary that shows the specific amount of values a combination of same-sided dice can possibly roll.

Example output for three 6-sided dice

input: 6,3
Desired output: {3: 1, 4: 3, 5: 6, 6: 10, 7: 15, 8: 21, 9: 25, 10: 27, 11: 27, 12: 25, 13: 21, 14: 15, 15: 10, 16: 6, 17: 3, 18: 1}

Example output for four 8-sided dice

input: 8,4
desired output: {4: 1, 5: 4, 6: 10, 7: 20, 8: 35, 9: 56, 10: 84, 11: 120, 12: 161, 13: 204, 14: 246, 15: 284, 16: 315, 17: 336, 18: 344, 19: 336, 20: 315, 21: 284, 22: 246, 23: 204, 24: 161, 25: 120, 26: 84, 27: 56, 28: 35, 29: 20, 30: 10, 31: 4, 32: 1}

Here is my function that creates an empty dictionary for each combination:

def dice_range(dice_type,dice_count):
    dice_dict = {i+1:0 for i in range(dice_type*dice_count) if i+1 >= dice_count}
    return dice_dict

input: dice_range(8,3)
actual output: {3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0, 11: 0, 12: 0, 13: 0, 14: 0, 15: 0, 16: 0, 17: 0, 18: 0, 19: 0, 20: 0, 21: 0, 22: 0, 23: 0, 24: 0}

With that I am able to figure out how to solve for a specific number of dice_count of any dice_type(# of sides) Here is the solution for the first couple of examples:

dice_type = 6
dice_count = 3
temp = dice_range(dice_type,dice_count)
# for 3 dice of any number of sides
for x in range(1,dice_type+1):
    for i in range(1,dice_type+1):
        for j in range(1,dice_type+1):
            for k,v in temp.items():
                if x+i+j == k:
                    temp[k] +=1
               
        
dice_type = 8
dice_count = 4
temp = dice_range(dice_type,dice_count)
# for 4 dice of any number of sides
for y in range(1,dice_type+1):
    for x in range(1,dice_type+1):
        for i in range(1,dice_type+1):
            for j in range(1,dice_type+1):
                for k,v in temp.items():
                    if y+x+i+j == k:
                        temp[k] +=1

I hope that is enough context for the question.

Here is what I tried out, but for some reason the recursion is not working as I intended.

def dice_range(dice_type,dice_count):
    dice_dict = {i+1:0 for i in range(dice_type*dice_count) if i+1 >= dice_count}
    return dice_dict

def dice_value_calculator(dice_type,dice_count):
    
    PREDICTION = dice_range(dice_type,dice_count)
    
    # Tallies the number by 1 everytime it shows up in the loop.
    def fill_dict(total):
        for k in PREDICTION.keys():
            if total == k:
                PREDICTION[k] += 1
        
    def loop(temp_dice_count,loop_total = 0):
        
        for loop_i in range(1,(dice_type+1)):

            # Base Case | if the number of dice(dice_count) reaches 0 that means it reached the end of the recursion
            if temp_dice_count == 0:
                fill_dict(loop_total)
                print(PREDICTION)
                loop_total = 0
                
            # General Case / Recursive
            else: 
                loop_total += loop_i
                temp_dice_count -= 1
                loop(temp_dice_count, loop_total)
                
    loop(dice_count) # calls the loop function 
    return PREDICTION # returns the temp dictionary

print(dice_value_calculator(6,3))

This is the output I'm getting for three 6-sided dice

{3: 2, 4: 4, 5: 0, 6: 2, 7: 0, 8: 0, 9: 0, 10: 0, 11: 0, 12: 0, 13: 0, 14: 0, 15: 0, 16: 0, 17: 0, 18: 0}

Both the fill_dict() function and the dice_range() function work well on their own so it must be how I'm calling loop()

Any tips would be greatly appreciated. Please let me know if I need to clarify anything, this is my first time asking a question so I may have missed something.

Thanks in advance

Answer 1

You can use a mathematical formula for getting the count of such arrangements where lower bound, upper bound, and number of groups are described.

For the given case, we can take:

• Number of dice available = number of groups = k
• A die can have the least number as = 1
• A die can have the maximum number = Number of faces it has got = upper limit = m

Then, the dictionary needed can be obtained as:

from math import comb
def get_i(n,k,m):
    for i in range(n+1):
        if (n - k + i*m >= 0) and (n-k - i*m - m < 0):
            return i

def s_nkm(n,k,m):
    s=0
    for r in range( get_i(n,k,m) + 1):
        s+=(-1)**r * comb(k,r) * comb(n-r*m - 1, k-1)
    return s

def get_dict(m,k):
    d={}
    for n in range(k, m*k + 1):
        # n is total number of ones
        d[n] = s_nkm(n,k,m)
    return d

m,k = 8,4

print(get_dict(m,k))

Outputs:

{4: 1, 5: 4, 6: 10, 7: 20, 8: 35, 9: 56, 10: 84, 11: 120, 12: 161, 13: 204, 14: 246, 15: 284, 16: 315, 17: 336, 18: 344, 19: 336, 20: 315, 21: 284, 22: 246, 23: 204, 24: 161, 25: 120, 26: 84, 27: 56, 28: 35, 29: 20, 30: 10, 31: 4, 32: 1}

The mathematical equation is added below:

Here, grouping is done based on thinking that those indistinguishable items are ones(as we do in partitions)

Answer 2

There are at least four possible approaches to the question.

"How do I get the effect of dynamically controlling the number of for loops?"

For this, you want itertools.product. I initially closed the question as a duplicate because of this, however...

---

"How do I emulate rolling multiple dice and get the resulting histogram?"

You should not try to run through every possible result on each die. This is slow and unnecessary.

Instead: run through the dice one at a time, taking the results from previous iterations and adding up what would happen with the possible results for the current die.

Suppose for example that we have a result like {3: 1, 4: 3, 5: 6, 6: 10, 7: 15, 8: 21, 9: 25, 10: 27, 11: 27, 12: 25, 13: 21, 14: 15, 15: 10, 16: 6, 17: 3, 18: 1} from three six-sided dice. How can we get the result for four dice? Simple: we add 1 to each key in order to get the results for four dice if the last die roll is 1, add 2 for the results where the last roll is 2, etc. Then we just have to add the counts for each matching total.

The Python standard library provides collections.Counter to simplify this task. Rather than manually matching up dict keys and adding the corresponding values, it's a special kind of dict that does that automatically.

Let's make a function to add the results of a die to an existing collections.Counter. I'll write it out imperatively first:

from collections import Counter

def add_d6(original):
    # starting with an empty tally
    total = Counter()
    for last_roll in range(1, 7):
        # for each possible result of the last roll, add its effect
        total += Counter(
            # which we find by modifying the keys
            (rolls + last_roll, count)
            # in the original dict
            for rolls, count in original.items()
        )
    return total

Now we can understand purely descriptive code:

from collections import Counter

def add_d6(original):
    return sum(
        Counter(
            (rolls + last_roll, count)
            for rolls, count in original.items()
        )
        for last_roll in range(1, 7)
    )

Using this to compute the entire histogram is left as an exercise.

---

"What if I just want that result and don't care about the process?"

You can also just use math to compute the correct values. See @Vicrobot's answer. This approach is less flexible in that it assumes normal "dice" with faces numbered 1..N. That's good enough for normal use, and more direct.

---

"Okay, but I really want to do it recursively in order to practice recursion."

There are a few different ways to implement the recursion. The most naive will effectively emulate "dynamically controlling the number of for loops". You can do this by, among other possible strategies:

• passing the "subtotal" of dice rolled so far in the recursive process, forwards into the recursion.
• passing the histogram so far, forwards into the recursion. (Or having it available as a global, or closure, or instance attribute...)
• If there are no remaining dice, update the histogram. Otherwise, recurse.

This appears to be the approach you're attempting. There are multiple issues with the code:

1. fill_dice doesn't make sense; there's no reason to iterate over a dictionary to look for a key. Just use prediction[total] += 1.

2. If you want "zero dice" as your base case, then you should add the total to the dict once in that case. It seems like you're trying to avoid the issue by setting the loop total to zero after adding it, and then having fill_dice ignore the zeros (by searching for the 0 key and failing to find it). This is far too complex.

3. As a side note: since the base case you've designed doesn't conceptually involve looping, it should be outside of the loop. In general, when writing recursive code you should handle the base case first and get it out of the way. It should be as "separate" from the main recursion as possible.

4. The part that actually causes the bug:

                loop_total += loop_i
                temp_dice_count -= 1
                loop(temp_dice_count, loop_total)

As a general hint for recursion, do not modify local variables in order to set up the recursion! The problem is that, after the recursive call returns, those modifications will still be in effect, and will accumulate as you work through the loop - which is not what you want.

Corrected code is much simpler:

def dice_value_calculator(dice_type,dice_count):
    histogram = dice_range(dice_type,dice_count)
        
    def loop(temp_dice_count,loop_total = 0): 
        if temp_dice_count == 0:
            histogram[loop_total] += 1
            return
        # Otherwise, iterate over die results and recurse for each one.
        for loop_i in range(1, dice_type + 1):
            loop(temp_dice_count - 1, loop_total + loop_i)
                
    loop(dice_count)
    return histogram

"But why is it so slow?" (On my machine, about 3/4 of a second to "roll" 5d20) Because of what I said way at the top. You can fix this by taking a fast iterative approach - like the Counter one shown above - and converting it to recursion mechanically. Alternately, you can modify the code so that a new histogram is returned at each recursive step (yes, this is initially even slower) and then applying memoization. Python makes this trivial, using the @functools.cache (in 3.8 and earlier, @functools.lru_cache(maxsize=None)) decorator.