Je travaille sur un programme de probabilité de dés et j'ai rencontré des problèmes d'efficacité dans la section de permutation lorsque les nombres grossissent. Par exemple, les périmètres que je dois exécuter sont 10 dés, avec 10 côtés, avec un résultat de 50.
J'ai besoin d'un nombre total de permutations pour calculer la probabilité du résultat spécifié étant donné le nombre de dés et le nombre de côtés. La fonction final_count (total, dés, faces) laisse passer le plus petit nombre de combinaisons du générateur avant de passer à la fonction perms (x) .
Le code suivant fonctionne, mais pour les périmètres mentionnés précédemment, cela prend un temps extrêmement long.
Le perms (x) a été publié par @Ashish Datta à partir de ce fil:
permutations avec des valeurs uniques
C'est là que je crois 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é des algorithmes de permutation avec python . Je pense 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- total de dés . Je me rends compte que je marche sur une ligne fine entre une question et une révision de code, mais je pense que dans ce cas, je suis plus du côté des questions :)
3 Réponses :
Vous pouvez utiliser une fonction qui déduit les lancers de dés actuels des totaux des appels récursifs, et court-circuite 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:
final_count(50, 10, 10)
afin que:
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))
renvoie dans une seconde: 374894389
C'est fantastique! Certainement au-dessus de ma tête, mais c'est comme ça que nous apprenons :) Je ne peux pas importer lru_cache pour une raison quelconque. functools n'est pas un tiers n'est-ce pas?
Heureux d'avoir pu aider. functools.lru_cache n'est disponible que depuis Python 3.3, donc si vous utilisez une version antérieure de Python, vous devrez installer un backport de celui-ci.
BINGO! ATOM utilise par défaut python2 -> corrigé. Je vous remercie. Merci d'avoir publié ça. Je vais voir si je peux creuser dans le processus dans pythontutor pour voir comment tout cela se passe.
J'avais une solution similaire à blhsing mais il m'a battu et, pour être honnête, je n'ai pas pensé à utiliser lru_cache (sympa! +1 pour ça). Je le poste quand même, ne serait-ce que pour illustrer comment le stockage des décomptes précédemment calculés réduit la récursivité.
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
Je n'ai pas pu importer lru_cache pour une raison quelconque, alors j'ai essayé le vôtre. Cela a fonctionné à merveille, sauf si la cible est 0. Facilement corrigé pour mes besoins, mais j'ai pensé mentionner le bogue.
Correction de cela pour référence future.
Une façon de réduire considérablement le temps est de compter mathématiquement le nombre de combinaisons pour chaque groupe unique de nombres dans combinaisons , et d'incrémenter count de ce montant. Si vous avez une liste de n objets où x1 d'entre eux sont tous identiques, x2 d'entre eux sont tous identiques, etc., alors le nombre total de façons de les organiser est n! / (X1! X2! X3! ...) . Par exemple, le nombre de manières différentes d'organiser les lettres de "Tennessee" est de 9! / (1! 4! 2! 2!). Vous pouvez donc créer une fonction distincte pour ceci:
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)
Je ne sais pas d'emblée s'il existe déjà une fonction intégrée qui fait le travail de ce que j'ai écrit comme indiv_combos2 , mais vous pouvez également utiliser Counter pour faire le comptage et mul pour prendre le produit d'une liste:
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 suis pas sûr du problème que vous essayez de résoudre. S'agit-il de toutes les permutations (ou combinaisons) de 10D10 qui totalisent 50? Si tel est le cas, vous passez beaucoup de temps à générer et vérifier toutes les combinaisons. Au contraire, un algorithme récursif "somme-à-cible" pourrait réduire ce temps.
Je vous remercie. J'ai édité ma question pour clarifier. J'ai besoin d'un nombre total de permutations pour calculer la probabilité des périmètres. trouver les combinaisons uniques ne prend que 0,42 s
@Prune Je pense que j'utilise une approche "somme-à-cible" en créant un générateur de combinaisons et en y accédant pour mes fonctions. Sauf si je ne comprends pas ce que cela signifie.
Non, mais la réponse que vous avez acceptée est exactement cette classe d'algorithme.