如何更快地迭代十个列表（每个十个元素）的笛卡尔积？ （概率与骰子）
How to iterate through the Cartesian product of ten lists (ten elements each) faster? (Probability and Dice)
我正在尝试解决 this task。
我为此写了 function，它使用 itertools.product() 作为输入迭代的笛卡尔积：
def probability(dice_number, sides, target):
from itertools import product
from decimal import Decimal
FOUR_PLACES = Decimal('0.0001')
total_number_of_experiment_outcomes = sides ** dice_number
target_hits = 0
sides_combinations = product(range(1, sides+1), repeat=dice_number)
for side_combination in sides_combinations:
if sum(side_combination) == target:
target_hits += 1
p = Decimal(str(target_hits / total_number_of_experiment_outcomes)).quantize(FOUR_PLACES)
return float(p)
当调用 probability(2, 6, 3) 时输出是 0.0556，所以工作正常。
但是调用 probability(10, 10, 50) 计算时间很长（几个小时？），但必须有更好的方法:)
for side_combination in sides_combinations: 需要很长时间才能遍历大量 sides_combinations.
拜托，你能帮我看看如何加快结果的计算吗，我今晚也想睡觉..
我猜想问题是求骰子总和的分布。一种有效的方法是通过离散卷积。变量总和的分布是它们的概率质量函数（或密度，在连续情况下）的卷积。卷积是一个 n 元运算符，因此您可以方便地一次只计算两个 pmf（目前的总数分布，以及列表中的下一个）。然后从最终结果中，您可以读出每个可能总数的概率。结果中的第一个元素是最小可能总数的概率，最后一个元素是最大可能总数的概率。在这两者之间，您可以找出哪一个对应于您要查找的特定金额。
这个最难的部分是卷积，所以先处理它。这只是一个简单的求和，只是要正确求和的极限有点棘手。我的建议是使用整数或有理数，这样你就可以进行精确的算术运算。
之后你只需要为每个输入芯片构造一个合适的pmf。输入只是 [1, 1, 1, ... 1] 如果你使用整数（你最终必须归一化）或 [1/n, 1/n, 1/n, ..., 1 /n] 如果有理数，其中 n = 面数。此外，您还需要正确标记输出的索引——同样，要做到这一点有点棘手。
卷积是一种非常通用的变量求和方法。由于 FFT(conv(A, B)) = FFT(A) FFT(B)，因此通过快速傅里叶变换实现卷积可以使其更加高效。但在这一点上，我认为你不需要担心这个。
如果有人仍然对通过所有 itertools.product 笛卡尔积避免非常非常非常长的迭代过程的解决方案感兴趣，这里是：
def probability(dice_number, sides, target):
if dice_number == 1:
return (1 <= target <= sides**dice_number) / sides
return sum([probability(dice_number-1, sides, target-x) \
for x in range(1,sides+1)]) / sides
但是你应该添加 probability 函数结果的缓存，如果你不这样做的话——概率的计算也会花费非常非常非常长的时间）
P.S。这个代码 100% 不是我的，我是从网上拿来的，我不是很聪明自己制作它，希望你会像我一样喜欢它。
我正在尝试解决 this task。
我为此写了 function，它使用 itertools.product() 作为输入迭代的笛卡尔积：
def probability(dice_number, sides, target):
from itertools import product
from decimal import Decimal
FOUR_PLACES = Decimal('0.0001')
total_number_of_experiment_outcomes = sides ** dice_number
target_hits = 0
sides_combinations = product(range(1, sides+1), repeat=dice_number)
for side_combination in sides_combinations:
if sum(side_combination) == target:
target_hits += 1
p = Decimal(str(target_hits / total_number_of_experiment_outcomes)).quantize(FOUR_PLACES)
return float(p)
当调用 probability(2, 6, 3) 时输出是 0.0556，所以工作正常。
但是调用 probability(10, 10, 50) 计算时间很长（几个小时？），但必须有更好的方法:)
for side_combination in sides_combinations: 需要很长时间才能遍历大量 sides_combinations.
拜托，你能帮我看看如何加快结果的计算吗，我今晚也想睡觉..
我猜想问题是求骰子总和的分布。一种有效的方法是通过离散卷积。变量总和的分布是它们的概率质量函数（或密度，在连续情况下）的卷积。卷积是一个 n 元运算符，因此您可以方便地一次只计算两个 pmf（目前的总数分布，以及列表中的下一个）。然后从最终结果中，您可以读出每个可能总数的概率。结果中的第一个元素是最小可能总数的概率，最后一个元素是最大可能总数的概率。在这两者之间，您可以找出哪一个对应于您要查找的特定金额。
这个最难的部分是卷积，所以先处理它。这只是一个简单的求和，只是要正确求和的极限有点棘手。我的建议是使用整数或有理数，这样你就可以进行精确的算术运算。
之后你只需要为每个输入芯片构造一个合适的pmf。输入只是 [1, 1, 1, ... 1] 如果你使用整数（你最终必须归一化）或 [1/n, 1/n, 1/n, ..., 1 /n] 如果有理数，其中 n = 面数。此外，您还需要正确标记输出的索引——同样，要做到这一点有点棘手。
卷积是一种非常通用的变量求和方法。由于 FFT(conv(A, B)) = FFT(A) FFT(B)，因此通过快速傅里叶变换实现卷积可以使其更加高效。但在这一点上，我认为你不需要担心这个。
如果有人仍然对通过所有 itertools.product 笛卡尔积避免非常非常非常长的迭代过程的解决方案感兴趣，这里是：
def probability(dice_number, sides, target):
if dice_number == 1:
return (1 <= target <= sides**dice_number) / sides
return sum([probability(dice_number-1, sides, target-x) \
for x in range(1,sides+1)]) / sides
但是你应该添加 probability 函数结果的缓存，如果你不这样做的话——概率的计算也会花费非常非常非常长的时间）
P.S。这个代码 100% 不是我的，我是从网上拿来的，我不是很聪明自己制作它，希望你会像我一样喜欢它。