Coincé à TIME COMPLEXITY, J'ai besoin d'une solution moins complexe pour générer des polygones à partir d'une liste donnée de longueur d'arête

Question

J'ai écrit un code pour compter le nombre de polygones pouvant être créés à partir des bâtonnets donnés (ie: longueurs).

pour les bâtonnets = [2, 3, 4, 5, 6], la sortie doit être polygonsCount (sticks) = 13.

Voici les polygones qui peuvent être obtenus à partir des clés avec longueurs 2, 3, 4, 5, et 6:

(2, 3, 4); 
(3, 4, 5); 
(2, 4, 5); 
(2, 5, 6); 
(3, 4, 6); 
(3, 5, 6); 
(4, 5, 6); 
(2, 3, 4, 5); 
(2, 3, 4, 6); 
(2, 3, 5, 6); 
(2, 4, 5, 6); 
(3, 4, 5, 6); 
(2, 3, 4, 5, 6); 

le programme fonctionne bien mais, en raison de la complexité du temps qu'il traverse le temps limite pour les listes supérieures.

D'abord j'ai généré un ensemble de puissance des listes données de bâtons. J'ai essayé d'éviter [] à tous les sous-ensembles d'éléments [x, x] - 2, mais j'ai échoué, aussi, je ne pense pas que cela réduira la complexité temporelle. Ensuite, je vérifie les polygones possibles. Mais je reçois la limite de temps. Voici le code:

def powersetGenerator(sticks,blankSet): 
    if sticks ==[]: 
     yield blankSet 
    else: 
     for item in powersetGenerator(sticks[1:],blankSet+[sticks[0]]): 
      yield item 
     for item in powersetGenerator(sticks[1:],blankSet): 
      yield item 

def possiblePolygons(array): 
    sumOfAll = sum(array) 
    longestSide = max(array) 
    return longestSide < sumOfAll - longestSide 

def polygonsCount(sticks): 
    powerset = list(powersetGenerator(sticks,[])) 
    count = 0 
    for index in range(len(powerset)): 
     if len(powerset[index])>=3 and possiblePolygons(powerset[index]) == 1: 
      count=(count+1)%((10**9) + 7) 
    return count 

Answer 1

Une alternative serait d'utiliser itertools.combinations() de la bibliothèque standard de Python pour générer les polygones:

def polygonGenerator(sticks): 
    for r in range(3, len(sticks)+1): 
     polygons = itertools.combinations(sticks, r) 
     # for lexicographical order & pretty printing 
     polygons = list(set(polygons)) 
     polygons.sort() 
     # 
     for polygon in polygons: 
      yield polygon 

pour python3 sans lexicographique commande polygonGenerator () peut être à remaniée avec:

def polygonGenerator(sticks): 
    for r in range(3, len(sticks)+1): 
     yield from set(itertools.combinations(sticks, r)) 

Answer 2

Ceci est fondamentalement la même façon lution avec la même complexité mais avec beaucoup d'optimisations afin d'éviter des opérations répétées.

# updated version 
import functools 

@functools.lru_cache(None) 
def s_s_l(items): 
    """return a list of items [subset, sum, length]""" 
    if not items: 
     return [[[], 0, 0]] 
    first, *rest = items # python3 syntax 
    ss1 = s_s_l(tuple(rest)) 
    ss2 = [[[first]+ss[0], first+ss[1], 1+ss[2]] for ss in ss1] 
    return ss1 + ss2 

def polygons(sticks): 
    """yield polygons""" 
    sticks = sorted(sticks, reverse=True) 
    prev_longest = None 
    for i in range(len(sticks)-2): 
     longest = sticks[i] 
     if longest == prev_longest: 
      continue 
     prev_longest = longest 
     for subset, nsum, nlen in s_s_l(tuple(sticks[i+1:])): 
      if nsum > longest and nlen >= 2: 
       yield([longest] + subset) 

def count_pg(sticks): 
    """count unique polygons""" 
    solutions = {tuple(pg) for pg in polygons(sticks)} 
    return len(solutions) 

print(count_pg([2, 3, 4, 5, 6])) 
print(count_pg([88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88])) 

---

Je peux me tromper, mais la clé d'une bonne solution pourrait être dans le calcul du nombre sans construire les polygones. Quelqu'un avec une meilleure base mathématique pourrait connaître la réponse.