Powerset-Funktion nicht genügend Arbeitsspeicher

Question

def powerset(x): 
    total1 = [[]] 
    total2 = [[]] 
    for a in x: 
     for b in total1: 
      c = list(b + [x[a]]) 
      total2.append(c) 
     total1 = total2 
     # the total 1 and total 2 system should prevent it 
     # from creating an infinite loop when we add to the total. 

     print (total1) 

f = [1,2,3] 
g = powerset(f) 
print (g) 

Hier ist mein Versuch, ein Powerset für ein Intro Data Science-Klasse zu erstellen. Wenn ich das ausführe, erhalte ich als Ausgaben, bevor der Speicher ausgeht. Ich verstehe nicht, warum es [[], [2]] zurückgibt, noch warum es nicht genügend Speicher hat, da Summe 1 außerhalb der Schleife geändert wird.

g sollte einen Leistungssatz von f zurückgeben.

könnte jemand erklären, was ich falsch mache?

Answer 1

Nach der ersten Schleife Sie total1 = total2 eingestellt, so dass bedeutet, dass total1 und total2 auf derselben Liste nach.

Und so iterieren Sie in der zweiten Schleife über total1 und aktualisieren total2, die gleiche Liste. In Python (und in den meisten Programmiersprachen) ist es gefährlich, alter eine Sammlung Sie iterieren über, so dass Sie fügen Sie Elemente auf der Liste, so dass die Schleife länger und länger.

Der Code ist nicht per se problematisch. Wir können schreiben Sie es als:

def powerset(x): 
    result = [[]] 
    for xi in x: 
     xil = [xi] 
     for j in range(len(result)): 
      result.append(result[j] + xil) 
    return result 

Obwohl es wie einige syntaktische Neufassungen aussehen, hier wir j über die range(len(result)) laufen. Beachten Sie, dass wir len(result)nur einmal berechnen, wenn wir die for Schleife starten, können wir danach sicher total aktualisieren, da sich das Bereichsobjekt nicht mehr ändert.

Diese dann ergibt sich:

>>> powerset([1,2,3]) 
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 

Beachten Sie, dass wir die itertools.combinations Funktion erleichtern das Leben verwenden können:

from itertools import combinations 

def powerset(x): 
    xl = list(x) 
    for r in range(len(xl)+1): 
     for ri in combinations(xl, r): 
      yield ri 

Wir erhalten dann:

>>> list(powerset([1,2,3])) 
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]