计算公平掷骰子的概率（非指数时间）

Question

这方面的变化是很常见的问题，但我所有的 google-fu 都让我难住了。我想计算掷骰子公平的几率，但我想有效地做到这一点。有很多关于如何做到这一点的例子，但我发现的所有算法在计算上都过于昂贵（指数时间），无法用于大量具有多面的骰子。

简单问题：计算 xy 面骰子上 n 卷的几率。

简单的解决方案：创建滚动的 n 元笛卡尔积，对每个乘积求和，计算和作为目标的次数，做一点除法，瞧。

Go 中的简单解决方案示例： https : //play.golang.org/p/KNUS4YBQC0g

简单的解决方案完美地工作。我将其扩展为允许丢弃最高/最低的 n 个面等情况，结果经得起现场测试。

但是考虑一下{Count: 20,Sides: 20,DropHighest: 0,DropLowest:0, Target: 200}。

如果我用以前的解决方案评估它，我的“表”将有 104 个奇怪的 septillion 单元，并且很容易使 CPU 达到最大值。

有没有更有效的方法来计算大量多面骰子的概率？如果是这样，它是否可以解释更复杂的“成功”条件选择，例如丢骰子？

由于这个美丽网站的存在，我相信这是可能的：https : //anydice.com/program/969

编辑：

最适合我的解决方案是 David Eisenstat 的答案，我将其移植到：https : //play.golang.org/p/cpD51opQf5h

Answer 1

下面是一些处理低滚和高滚的代码。抱歉切换到 Python，但我需要简单的 bignum 和记忆库来保持理智。我认为复杂性是这样的O(count^3 sides^2 drop_highest)。

这段代码的工作方式是用掷骰子的可能性空间count除以sides显示最大数字的骰子数量 ( count_showing_max)。有多种binomial(count, count_showing_max)方法可以在带有独特标签的骰子上实现这种掷骰，因此multiplier. 给定count_showing_max，我们可以算出有多少个最大骰子因高而被丢弃，有多少因低而被丢弃（确实如此），并将这个总和添加到剩余骰子的结果中。

#!/usr/bin/env python3
import collections
import functools
import math


@functools.lru_cache(maxsize=None)
def binomial(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))


@functools.lru_cache(maxsize=None)
def outcomes(count, sides, drop_highest, drop_lowest):
    d = collections.Counter()
    if count == 0:
        d[0] = 1
    elif sides == 0:
        pass
    else:
        for count_showing_max in range(count + 1):  # 0..count
            d1 = outcomes(count - count_showing_max, sides - 1,
                          max(drop_highest - count_showing_max, 0),
                          drop_lowest)
            count_showing_max_not_dropped = max(
                min(count_showing_max - drop_highest,
                    count - drop_highest - drop_lowest), 0)
            sum_showing_max = count_showing_max_not_dropped * sides
            multiplier = binomial(count, count_showing_max)
            for k, v in d1.items():
                d[sum_showing_max + k] += multiplier * v
    return d


def main(*args):
    d = outcomes(*args)
    denominator = sum(d.values()) / 100
    for k, v in sorted(d.items()):
        print(k, v / denominator)


if __name__ == '__main__':
    main(5, 6, 2, 2)