Comment affiner les permutations de nombres pour plus d'efficacité ?

Question

Je travaille sur un programme de probabilité pour les dés et j'ai rencontré quelques problèmes d'efficacité dans la section de permutation lorsque les nombres deviennent grands. Par exemple, les périmètres que je dois exécuter sont 10 dés, avec 10 faces, avec un résultat de 50.

J'ai besoin d'un nombre total de permutations pour calculer la probabilité du résultat spécifié compte tenu du nombre de dés et du nombre de faces. Le site final_count(total, dice, faces) laisse passer le plus petit nombre de combinaisons du générateur avant de passer dans la fonction perms(x) fonction.

Le code suivant fonctionne, mais pour les périmètres mentionnés précédemment, il prend un temps extrêmement long.

En perms(x) a été posté par @Ashish Datta à partir de ce fil : permutations avec des valeurs uniques C'est là que je pense avoir besoin d'aide.

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

J'ai lu le fil de discussion Comment améliorer l'efficacité de l'algorithme de permutation avec python . Je crois que ma question est différente, bien qu'un algorithme plus intelligent soit mon objectif final.

J'ai initialement publié ma première ébauche de ce programme dans CodeReview. https://codereview.stackexchange.com/questions/212930/calculate-probability-of-dice-total . Je me rends compte que je suis sur la corde raide entre une question et un examen du code, mais je pense que dans ce cas, je suis plus du côté des questions :)

Answer 1

Vous pouvez utiliser une fonction qui déduit les jets de dés actuels des totaux pour les appels récursifs, et court-circuiter la recherche si le total est inférieur à 1 ou supérieur au nombre de dés multiplié par le nombre de faces. Utilisez un cache pour éviter les calculs redondants des mêmes paramètres :

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

de sorte que :

final_count(50, 10, 10)

revient dans la seconde : 374894389

Answer 2

J'avais une solution similaire à blhsing mais il m'a devancé et, pour être honnête, je n'ai pas pensé à utiliser lru_cache (sympa ! +1 pour ça). Je la poste quand même, ne serait-ce que pour illustrer comment le stockage des comptages précédemment calculés réduit la récursion.

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

Une façon de réduire considérablement le temps est de compter mathématiquement le nombre de combinaisons possibles pour chaque groupe unique de nombres dans la base de données. combinations et incrémenter count de ce montant. Si vous avez une liste de n objets où x1 d'entre eux sont tous semblables, x2 d'entre eux sont tous semblables, etc., alors le nombre total de façons de les disposer est n!/(x1 ! x2 ! x3 ! ...). Par exemple, le nombre de façons différentes de disposer les lettres de "Tennessee" est de 9!/(1 ! 4 ! 2 ! 2 !). Vous pouvez donc créer une fonction distincte pour cela :

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

Je ne sais pas s'il existe déjà une fonction intégrée qui fait le travail de ce que j'ai écrit en tant que indiv_combos2 mais vous pouvez aussi utiliser Counter pour faire le comptage et mul pour prendre le produit d'une liste :

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)

J'obtiens des résultats mitigés les fois où j'essaie les deux méthodes avec (25, 10, 10) comme entrée, mais les deux me donnent la réponse en moins de 0,038 secondes à chaque fois.