How to refine number permutations for efficiency

Question

I am working on a dice probability program and have been running into some efficiency issues in the permutation section when the numbers get big. For example, the perimeters I am required to run are 10 dice, with 10 sides, with an outcome of 50.

I require a total number of permutations to calculate the probability of the specified outcome given the number of dice and number of sides. The final_count(total, dice, faces) function lets the least number of combinations pass from the generator before moving into the perms(x) function.

The following code works, but for the previously mentioned perimeters it takes an extremely long time.

The perms(x) was posted by @Ashish Datta from this thread: permutations with unique values Which is where I believe I need help.

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

I have read the thread How to improve permutation algorithm efficiency with python. I believe my question is different, though a smarter algorithm is my end goal.

I originally posted my first draft of this program in CodeReview. https://codereview.stackexchange.com/questions/212930/calculate-probability-of-dice-total. I realize I am walking a fine line between a question and a code review, but I think in this case, I am more on the question side of things :)

Answer 1

You can use a function that deducts the current dice rolls from the totals for the recursive calls, and short-circuit the search if the total is less than 1 or greater than the number of dices times the number of faces. Use a cache to avoid redundant calculations of the same parameters:

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

so that:

final_count(50, 10, 10)

returns within a second: 374894389

Answer 2

I had a similar solution to blhsing but he beat me to it and, to be honest I didn't think of using lru_cache (nice! +1 for that). I'm posting it anyhow if only to illustrate how storage of previously computed counts cuts down on the recursion.

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

One way to greatly reduce the time is to mathematically count how many combinations there are for each unique group of numbers in combinations, and increment count by that amount. If you have a list of n objects where x1 of them are all alike, x2 of them are all alike, etc., then the total number of ways to arrange them is n!/(x1! x2! x3! ...). For example, the number of different ways to arrange the letters of "Tennessee" is 9!/(1! 4! 2! 2!). So you can make a separate function for this:

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

I don't know off-hand if there's already some built-in function that does the job of what I wrote as indiv_combos2, but you could also use Counter to do the counting and mul to take the product of a list:

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)

I get mixed results on the times when I try both methods with (25, 10, 10) as the input, but both give me the answer in less than 0.038 seconds every time.