# How to use recursion to deal with variable numbers of nested for loop?

Stack Overflow Asked by Jacky Chan on December 9, 2020

I am dealing with the following question:

Create a function that accepts two arguments, the number of dice rolled, and the outcome of the roll. The function returns the number of possible combinations that could produce that outcome. The number of dice can vary from 1 to 6.

And below is my code for 4 dice (x=4). But I am not able to extend this to any number of dices (x).

def dice_roll(x, y):
all_comb = []
for i in range(1, 7):
for j in range(1, 7):
for q in range(1, 7):
for r in range(1, 7):
total = i+j+q+r
all_comb.append(total)

return all_comb.count(y)


Is there a way to use recursion to deal with variable numbers of nested loops? And are there other more elegant ways apart from recursion for this question?

def combin_list(n):
# n is number of dice
if n == 1:
return [1,2,3,4,5,6]
else:
temp = combin_list(n-1)
resualt = []
for i in range(1,7):
for item in temp:
resualt.append(i+item)
return resualt
def dice_roll(x, y):
list = combin_list(x)
return list.count(y)


Correct answer by hr.mousavi on December 9, 2020

Here's a version that calculates the number of rolls for each total in O(n*s) time where n is the number of dice, and s the number of sides. It uses O(n) storage space.

If R[k, t] is the number of rolls of k dice that total t (keeping the number of sides fixed), then the recurrence relations are:

 R[0, t] = 1 if t=0, 0 otherwise
R[k, t] = 0 if t < 0
R[k, t] = R[k-1, t-1] + R[k-1, t-2] + ... + R[k-1, t-s]


Then we solving this with dynamic programming.

def dice_roll(n, sides):
A =  +  * (sides * n)
for k in range(n):
T = sum(A[k] for k in range(max(0, sides*k), sides*(k+1)))
for i in range(sides*(k+1), -1, -1):
A[i] = T
if i > 0:
T -= A[i-1]
if i - sides - 1 >= 0:
T += A[i - sides - 1]
return A

print(dice_roll(9, 4))


The program returns an array A with A[i] storing the number of ways of rolling n dice with s sides that sum to i.

Answered by Paul Hankin on December 9, 2020

a more mathematical approach using sympy.

for larger numbers of dice this will scale way better than iterating over all possibilities; for small numbers of dice the start-up time of sympy will probably not be worth the trouble.

from sympy.utilities.iterables import partitions, multiset_permutations

def dice_roll(n_dice, total):
ret = 0
for item in partitions(total, k=6, m=n_dice):
if sum(item.values()) != n_dice:
continue
print(f"{item}")

# this for loop is only needed if you want the combinations explicitly
for comb in multiset_permutations(item):
print(f"  {comb}")

ret += sum(1 for _ in multiset_permutations(item))
return ret


i get the number of partitions of total first (limiting the maximum value with k=6 as needed for a dice) and then count the number of possible multiset partitions.

the example:

r = dice_roll(n_dice=3, total=5)
print(r)


outputs:

{3: 1, 1: 2}
[1, 1, 3]
[1, 3, 1]
[3, 1, 1]
{2: 2, 1: 1}
[1, 2, 2]
[2, 1, 2]
[2, 2, 1]
6


meaning there are 6 ways to get to 5 with 3 dice. the combinations are shown.

in order to speed up things you could calculate the number of multiset combinations directly (you loose the explicit representation of the possibilities, though):

from sympy.utilities.iterables import partitions, multiset_permutations
from math import comb

def number_multiset_comb(dct):
ret = 1
n = sum(dct.values())  # number of slots
for v in dct.values():
ret *= comb(n, v)
n -= v
return ret

def dice_roll(n_dice, total):
ret = 0
for item in partitions(total, k=6, m=n_dice):
if sum(item.values()) != n_dice:
continue
ret += number_multiset_comb(dct=item)
return ret


Answered by hiro protagonist on December 9, 2020

As mentioned in the comments you should use itertools.product like this:

import itertools

def dice_roll(dices: int, result: int) -> int:
combos = [x for x in itertools.product(range(1, 7), repeat=dices) if sum(x) == result]
return len(combos)
# combos = [(1, 3), (2, 2), (3, 1)]

if __name__ == '__main__':
print(dice_roll(2, 4))
# returns 3


With itertools.product you get all possible combinations of the given amount of dices. with the list comprehension we filter the values by the correct sum.

Answered by D-E-N on December 9, 2020

## Related Questions

### Is there way to destruct elements in js more shorter and clean?

1  Asked on December 9, 2021 by andrii-yakymyshyn

### Is my code correct to find a prime number by means of recursion in python? or is the answer key?

3  Asked on December 9, 2021 by saleh

### Why an abstract class is “considered incomplete”?

3  Asked on December 9, 2021 by locobe

### Jquery promises in loop

1  Asked on December 9, 2021 by alan-a

### Vertical align on left Boostrap

1  Asked on December 9, 2021 by obsesie

### Why JMM produces (0, 0) even though it is considered a forbidden result

1  Asked on December 9, 2021

### How to get flags of opened fd in C?

2  Asked on December 9, 2021 by code_worker

### Make list evenly spaced and inline

4  Asked on December 9, 2021 by nobert

### Multiple inheritance from library in C++ with ambiguity

0  Asked on December 9, 2021 by thorolin

### ASP Core 3.1 API with EF Core 5.0

1  Asked on December 9, 2021 by bibout182

### Using set in c++ standard template library (STL)

1  Asked on December 9, 2021 by tushar-jain

### Element goes out of the element in JS

1  Asked on December 9, 2021

### I am fairly new to STLs in C++ and i tried making a heap using vectors. Didnt get the desired output

3  Asked on December 9, 2021 by user11880529

### How to set scrollbars to only part of the modal?

2  Asked on December 9, 2021 by gowthamss

### C#, Linq, Filter a list whether its properties appear on another list

2  Asked on December 9, 2021 by hiedeptrai

### Return all filename from database by specific field name

4  Asked on December 9, 2021 by maqsud-inamdar

### How do I target the nearest div of a class with this nested HTML?

2  Asked on December 9, 2021 by m0a

### Call a class function from a async class function

2  Asked on December 9, 2021 by toge

### JS Variable Not Being Passed Correctly

1  Asked on December 9, 2021