python - 如何优化数字排列以提高效率

Question

我正在开发一个骰子概率程序，当数字变大时，我在排列部分遇到了一些效率问题。例如，我需要跑的周长是 10 个骰子，有 10 个面，结果为 50。

我需要排列总数来计算给定骰子数量和面数的指定结果的概率。 final_count(total, dice, faces) 函数让生成器传递最少数量的组合，然后再进入 perms(x) 函数。

下面的代码可以工作，但是对于前面提到的边界，它需要非常长的时间。

perms(x) 是由 @Ashish Datta 在该线程中发布的: permutations with unique values 我认为这就是我需要帮助的地方。

import itertools as it

total = 50
dice = 10
faces = 10

#-------------functions---------------------

# Checks for lists of ALL the same items
def same(lst):
   return lst[1:] == lst[:-1]

# Generates the number of original permutations (10 digits takes 1.65s)
def perms(x):
    uniq_set = set()
    for out in it.permutations(x, len(x)):
        if out not in uniq_set:
            uniq_set.update([out])
    return len(uniq_set)


# Finds total original dice rolls.  "combinations" = (10d, 10f, 50t, takes 0.42s)
def final_count(total, dice, faces):
    combinations = (it.combinations_with_replacement(range(1, faces+1), dice))
    count = 0
    for i in combinations:
        if sum(i) == total and same(i) == True:
            count += 1
        elif sum(i) == total and same(i) != True:
            count += perms(i)
        else:
            pass
    return count

# --------------functions-------------------

answer = final_count(total, dice, faces) / float(faces**dice)

print(round(answer,4))

我已阅读该主题 How to improve permutation algorithm efficiency with python 。我相信我的问题是不同的，尽管更智能的算法是我的最终目标。

我最初在 CodeReview 中发布了该程序的初稿。 https://codereview.stackexchange.com/questions/212930/calculate-probability-of-dice-total 。我意识到我在问题和代码审查之间走得很好，但我认为在这种情况下，我更倾向于问题方面:)

Answer 1

您可以使用一个函数，从递归调用的总数中扣除当前掷骰子的数量，如果总数小于 1 或大于骰子数量乘以面数，则可以短路搜索。使用缓存可以避免相同参数的冗余计算:

from functools import lru_cache
@lru_cache(maxsize=None)
def final_count(total, dice, faces):
    if total < 1 or total > dice * faces:
        return 0
    if dice == 1:
        return 1
    return sum(final_count(total - n, dice - 1, faces) for n in range(1, faces + 1))

这样:

final_count(50, 10, 10)

一秒内返回:374894389