Как улучшить числовые перестановки для эффективности

Question

Я работаю над программой вероятности игры в кости и столкнулся с некоторыми проблемами эффективности в секции перестановок, когда числа становятся большими.Например, я должен пройти по периметру 10 кубиков с 10 сторонами с результатом 50.

Мне требуется общее количество перестановок для расчета вероятности указанного исхода с учетом количества игральных костейи количество сторон.Функция final_count(total, dice, faces) позволяет наименьшему количеству комбинаций пройти от генератора до перехода в функцию perms(x).

Следующий код работает, но для ранее упомянутых периметров это занимает очень много времени.

@Ashish Datta опубликовал perms(x) из этой ветки: перестановки с уникальными значениями Вот где я считаю, что мне нужна помощь.

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

У меня естьПрочитайте ветку Как повысить эффективность алгоритма перестановки с помощью python .Я считаю, что у меня другой вопрос, хотя моей конечной целью является более умный алгоритм.

Первоначально я опубликовал свой первый черновик этой программы в CodeReview.https://codereview.stackexchange.com/questions/212930/calculate-probability-of-dice-total. Я понимаю, что провожу тонкую грань между вопросом и проверкой кода, но я думаю, что в этом случае меня больше интересует вопрос :))

Answer 1

У меня было похожее решение для 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 2

Один из способов значительно сократить время - это математически подсчитать, сколько комбинаций существует для каждой уникальной группы чисел в 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 секунды каждый раз.

Answer 3

Вы можете использовать функцию, которая вычитает текущие броски костей из итогов для рекурсивных вызовов и замыкает поиск, если сумма меньше 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