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

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

Answer 2

我有一个类似的解决方案blhsing但他打败了我，说实话我没想到使用lru_cache（很好！+1为此）。无论如何我只是为了说明先前计算的计数的存储如何减少递归而发布它。

def permutationsTo(target, dices, faces, computed=dict()):
    if target > dices*faces or target < 1: return 0 
    if dices == 1 :                        return 1
    if (target,dices) in computed: return computed[(target,dices)]
    result = 0 
    for face in range(1,min(target,faces+1)):
         result += permutationsTo(target-face,dices-1,faces,computed)
    computed[(target,dices)] = result
    return result  

Answer 3

大大减少时间的一种方法是在数学上计算combinations中每个唯一数字组的组合数量，并将count增加该数量。如果你有一个n个对象的列表，其中x1个都是相似的，x2个都是相似的，等等，那么排列它们的方法总数是n！/（x1！x2！x3！...） 。例如，排列“田纳西州”字母的不同方式的数量是9！/（1！4！2！2！）。所以你可以为此创建一个单独的函数：

import math
import itertools as it
import time

# Count the number of ways to arrange a list of items where
# some of the items may be identical.
def indiv_combos(thelist):
    prod = math.factorial(len(thelist))
    for i in set(thelist):
        icount = thelist.count(i)
        prod /= math.factorial(icount)
    return prod

def final_count2(total, dice, faces):
    combinations = it.combinations_with_replacement(range(1, faces + 1), dice)
    count = 0
    for i in combinations:
        if sum(i) == total:
            count += indiv_combos(i)
    return count

我不知道如果已经有一些内置函数完成我写的indiv_combos2的工作，但你也可以使用Counter进行计数和mul来获取列表的产品：

from operator import mul
from collections import Counter

def indiv_combos(thelist):
    return math.factorial(len(thelist)) / reduce(mul, [math.factorial(i) for i in Counter(thelist).values()],1)

当我尝试使用(25, 10, 10)作为输入的两种方法时，我得到了混合的结果，但是每次都在不到0.038秒的时间内给出答案。