appel sur le code récursif avec une complexité exponentielle d'une boucle

Question

Ce code est présenté comme un exemple de la complexité exponentielle dans un MIT programming course:

def genSubsets(L): 

    if len(L) == 0: 
     return [[]] #list of empty set 
    smaller = genSubsets(L[:-1]) #all subsets without last element 
    extra = L[-1:] #create a list of just the last element 
    new = [] 
    for small in smaller: 
     new.append(small+extra) #for all smaller solutions, add one with last element 
    return smaller+new #combine those with last element and those without 

Si je demande à genSubsets avec une liste régulière, je reçois une réponse comme prévu (un ensemble de tous les sous-ensembles possibles).

print(genSubsets([0,1,2])) 
#prints - [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]] 

Cependant, si je tente de l'appeler à partir d'une boucle (soit en utilisant la compréhension de la liste ou en construisant des listes à l'aide d'un sous-boucle), puis appelant genSubsets, la fonction ne retourne pas la réponse attendue .

for i in range(4): 
    L = [] 
    for j in range(i): 
     L.append(j) 
    #print(L) # works as expected 
    print(genSubsets([L])) # produces lists of length two regardless of number input list length 

Je veux faire appel à la fonction à partir de la boucle parce que je suis curieux de voir comment la taille (c.-à-longueur) de la liste retournée des sous-ensembles augmente à mesure que la taille d'entrée se développe et à l'expérience de la façon dont le traitement le temps augmente à mesure que la taille de la liste d'entrée augmente.

Answer 1

Eh bien, vous lui donnez une liste avec un seul élément, donc bien sûr, vous obtenez seulement deux sous-ensembles. Remplacez genSubsets([L]) par genSubsets(L).