我如何使用递归循环来查找在滚动任意数量的骰子和任意数量的面之间出现一个值的次数？

Question

我正在尝试编写一个函数来打印出一个字典，该字典显示同面骰子的组合可能掷出的特定数量的值。

三个 6 面骰子

的示例输出

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}

四个 8 面骰子

的示例输出

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}

这是我为每个组合创建一个空字典的函数：

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}

有了这个我就能够弄清楚如何解决任何dice_type（边数）的特定数量的dice_count 这是前几个示例的解决方案：

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

我希望这个问题的上下文足够了。

这是我尝试过的方法，但由于某种原因，递归没有按我的预期工作。


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

这是我得到的三个 6 面骰子

的输出

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

fill_dict() 函数和 dice_range() 函数都可以独立运行，所以这一定是我调用 loop()

的方式

如有任何提示，我们将不胜感激。如果我需要澄清任何事情，请告诉我，这是我第一次提问，所以我可能错过了一些东西。

提前致谢

Answer 1

您可以使用数学公式计算此类排列的数量，其中描述了下限、上限和组数。

对于给定的情况，我们可以采取：

可用骰子数=组数=k
一个骰子可以有最少的数字 = 1
一个骰子可以有的最大数量=它得到的面数=上限=m

那么，需要的字典可以这样获取：

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

输出：

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

下面添加数学方程式：

在这里，分组是基于认为那些无法区分的项目是一个（就像我们在分区中所做的那样）

Answer 2

这个问题至少有四种可能的方法。

“如何实现动态控制`for`循环次数的效果？”

为此，you want itertools.product。因此，我最初将问题作为重复问题关闭，但是...

“如何模拟掷多个骰子并获得结果直方图？”

您不应该尝试运行遍历每个骰子的所有可能结果。这很慢而且没有必要。

相反：运行一次一个地掷骰子，获取先前迭代的结果，然后相加当前骰子的可能结果会发生什么.

例如，假设三个 six-sided 骰子的结果类似于 {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}。我们怎样才能得到四个骰子的结果？简单：我们将每个键加 1 以获得四个骰子的结果 如果最后一次掷骰是 1，则为最后一次掷骰为 2 的结果加 2，等等。然后我们只需要为每个匹配的总数添加计数。

Python 标准库提供了 collections.Counter 来简化这个任务。它不是手动匹配 dict 键并添加相应的值，而是一种自动执行此操作的特殊类型的 dict。

让我们创建一个函数，将骰子的结果添加到现有 collections.Counter。我先命令式写出来：

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

现在我们可以理解纯描述性代码了：

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

使用它来计算整个直方图留作练习。

“如果我只想要结果而不关心过程怎么办？”

您也可以只使用数学来计算正确的值。请参阅@Vicrobot 的回答。这种方法不太灵活，因为它假定面编号为 1..N 的正常“骰子”。正常使用就够用了，而且更直接

“好吧，但我真的很想递归地做，以练习递归。”

有几种不同的方法可以实现递归。最幼稚的人会有效地模仿“动态控制 for 循环的数量”。您可以通过其他可能的策略来做到这一点：

传递到目前为止在递归过程中掷出的骰子的“小计”，前进到递归。
到目前为止通过直方图，转发到递归。（或者将其用作全局、闭包或实例属性...）
如果没有剩余的骰子，更新直方图。否则，递归。

这似乎是您正在尝试的方法。代码存在多个问题：

fill_dice 没有意义；没有理由遍历字典来查找键。只需使用 prediction[total] += 1.
如果你想要“零骰子”作为你的基本情况，那么你应该在这种情况下将总数添加到字典 once 中。似乎您试图通过在添加后将循环总数设置为零来避免此问题，然后让 fill_dice 忽略零（通过搜索 0 键但找不到它） .这太复杂了。
附带说明：由于您设计的基本情况在概念上不涉及循环，它应该在循环之外。通常，在编写递归代码时，您应该首先处理基本情况并将其排除在外。它应该尽可能与主递归“分开”。
实际导致错误的部分：

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

作为递归的一般提示，不要为了设置递归而修改局部变量！问题是，在递归调用 returns 之后，这些修改仍然有效，并且会在您完成循环时累积 - 这不是您想要的。

更正后的代码更简单：

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

“可是为什么这么慢？” （在我的机器上，大约 3/4 秒“滚动”5d20）因为我在顶部所说的方式。您可以通过采用快速迭代方法（如上面显示的 Counter 方法）并将其转换为递归 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 使用 @functools.cache（在 3.8 及更早版本中，@functools.lru_cache(maxsize=None)）装饰器使这变得微不足道。

我如何使用递归循环来查找在滚动任意数量的骰子和任意数量的面之间出现一个值的次数？

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?

python

recursion

loops

probability

dice

“如何实现动态控制`for`循环次数的效果？”

“如何模拟掷多个骰子并获得结果直方图？”

“如果我只想要结果而不关心过程怎么办？”

“好吧，但我真的很想递归地做，以练习递归。”

我如何使用递归循环来查找在滚动任意数量的骰子和任意数量的面之间出现一个值的次数？

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?

python

recursion

loops

probability

dice

“如何实现动态控制for循环次数的效果？”

“如何模拟掷多个骰子并获得结果直方图？”

“如果我只想要结果而不关心过程怎么办？”

“好吧，但我真的很想递归地做，以练习递归。”

“如何实现动态控制`for`循环次数的效果？”