compter Efficacement ensembles dans un produit cartésien cette somme au-dessus d'un certain nombre

Question

Je le dessous du code Python 3 qui fonctionne:

import itertools 

loops = 10 
results = [4, 2.75, 2.75, 1.5, 1.5, 1.5, 0] 
threshold = loops * 2 
cartesian_product = itertools.product(results, repeat=loops) 

good, bad = 0, 0 

for e in cartesian_product: 
    if (sum(e) >= threshold): 
     good += 1 
    else: 
     bad += 1 

print('Ratio of good vs total is {0:.3f}%'.format(100 * good/(good + bad))) 

Si j'augmente les boucles à un plus grand nombre (> 15), le programme prend trop long pour finir.

Existe-t-il un moyen/un algorithme plus efficace pour calculer le ratio?

Answer 1

Voici une solution. L'idée est de calculer toutes les sommes possibles de nos valeurs que vous pouvez obtenir avec n boucles, en comptant les différentes sommes possibles, et en comptant ensemble toutes les sommes supérieures au seuil.

Ensuite, nous pouvons générer toutes les sommes possibles pour n + 1 en ajoutant nos valeurs aux sommes précédentes. Nous pouvons espérer que le nombre de sommes différentes ne deviendra pas trop grand, car nous ajoutons plusieurs fois les mêmes valeurs, et nous regroupons toutes les sommes supérieures au seuil.

from collections import Counter 

def all_sums(values, threshold, previous_sums = None): 
    """ 
    values must be sorted 
    previous_sums is a Counter of previously obtained possible sums 

    Returns a Counter of all possible sums of values and the previous sums 
    """ 
    if not previous_sums: 
     previous_sums = Counter({0:1}) 

    new = Counter() 
    for existing_sum, ex_sum_count in sorted(previous_sums.items()): 
     for index, val in enumerate(values): 
      total = existing_sum + val 
      if total < threshold: 
       # With the current value, we have found ex_sum_count 
       # ways to obtain that total 
       new.update({total: ex_sum_count}) 
      else: 
       # We don't need the exact sum, as anything we could 
       # later add to it will be over the threshold. 
       # We count them under the value = threshold 
       # As 'values' is sorted, all subsequent values will also give 
       # a sum over the threshold 
       values_left = len(values) - index 
       new.update({threshold: values_left * ex_sum_count}) 
       break 
    return new 


def count_sums(values, threshold, repeat): 
    """ 
    values must be sorted! 

    Recursively calculates the possible sums of 'repeat' values, 
    counting together all values over 'threshold' 
    """ 
    if repeat == 1: 
     return all_sums(values, threshold, previous_sums=None) 
    else: 
     return all_sums(values, threshold, previous_sums=count_sums(values, threshold, repeat=repeat-1)) 

Essayons sur votre exemple:

loops = 10 
results = [4, 2.75, 2.75, 1.5, 1.5, 1.5, 0] 
threshold = loops * 2 

values = sorted(results) 

sums = count_sums(values, threshold, repeat=loops) 
print(sums) 
# Counter({20: 137401794, 19.75: 16737840, 18.25: 14016240, 18.5: 13034520, 19.5: 12904920, 
# 17.0: 12349260, 15.75: 8573040, 17.25: 8048160, 15.5: 6509160, 16.75: 6395760, 14.25: 5171040, 
# 18.0: 5037480, 14.5: 4461480, 16: 3739980, 18.75: 3283020, 19.25: 3220800, 13.0: 3061800, 
# 14.0: 2069550, 12.75: 1927800, 15.25: 1708560, 13.25: 1574640, 17.5: 1391670, 11.5: 1326780, 
# 11.75: 1224720, 14.75: 1182660, 16.5: 1109640, 10.25: 612360, 17.75: 569520, 11.25: 453600, 
# 16.25: 444060, 12.5: 400680, 10.0: 374220, 12: 295365, 13.75: 265104, 10.5: 262440, 19.0: 229950, 
# 13.5: 204390, 8.75: 204120, 15.0: 192609, 9.0: 153090, 8.5: 68040, 9.75: 65520, 7.5: 61236, 
# 7.25: 45360, 11.0: 44940, 12.25: 21840, 6.0: 17010, 7.0: 7560, 5.75: 6480, 8.25: 5280, 4.5: 3240, 
# 9.5: 2520, 10.75: 720, 4.25: 540, 5.5: 450, 3.0: 405, 6.75: 180, 8: 45, 1.5: 30, 2.75: 20, 4: 10, 0: 1}) 
number_of_sums = len(results) ** loops 
# 282475249 
good = sums[threshold] 
# 137401794 
bad = number_of_sums - good 
# 145073455 

je l'ai chronométré, il faut environ 9 ms sur ma machine assez ancienne.

Et avec d'autres données: 10 valeurs différentes, 20 boucles:

loops = 20 
results = [4, 2.75, 2.45, 1.5, 1.3, 0.73, 0.12, 1.4, 1.5, 0] 
threshold = loops * 2 
values = sorted(results) 

sums = count_sums(values, threshold, repeat=loops) 
number_of_sums = len(results) ** loops 
good = sums[threshold] 
bad = number_of_sums - good 
print(good) 
print(bad) 
# 5440943363190360728 
# 94559056636809639272 

que j'obtiens en moins de 12 secondes.