Erzeugen aller Teilmengen einer Menge

Bei der Bestimmung aller Teilmengen einer bestimmten Menge spielt die Anzahl der Elemente (n) eine entscheidende Rolle . Ein effektiver Algorithmus nutzt rekursive Techniken, um dies zu erreichen.

Rekursiver Algorithmus

Der rekursive Algorithmus basiert auf dem Prinzip, dass für jedes Element die Teilmengen in zwei Teile aufgeteilt werden können Kategorien: diejenigen, die das Element enthalten und diejenigen, die es ausschließen. Ansonsten teilen sich diese beiden Partitionen identische Teilmengen.

Beginnend mit n=1 haben wir zwei Teilmengen: {} (die leere Menge) und {1}.

Für n>1 bestimmen wir die Teilmengen von 1,...,n-1 und dupliziere sie. Einer Menge wird n zu jeder Teilmenge hinzugefügt, während die andere unverändert bleibt. Die Vereinigung dieser beiden Mengen ergibt die vollständige Menge der Teilmengen.

Anschauliches Beispiel

Generieren wir die Teilmengen von {1, 2, 3, 4, 5}:

• n=1: {{} , {1}}
• n=2: Nimm {} , {1} und addiere 2. Vereinigung mit {} , {1}: {{} , {1} , {2} , {1, 2}}
• n=3: Addiere 3: {{} , {1} , {2} , {1, 2}, {3} , {1, 3} , {2, 3} , {1, 2, 3}}
• n=4: Addiere 4: {{} , {1} , {2} , {1, 2} , {3} , {1, 3} , {2, 3} , {1, 2, 3}, {4} , {1, 4} , {2, 4} , {1, 2, 4} , {3, 4} , {1, 3, 4} , {2, 3, 4} , { 1, 2, 3, 4}}
• n=5: Addiere 5: {{} , {1} , {2} , {1, 2} , {3} , {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}, {5}, {1, 5}, {2, 5}, {1, 2, 5}, {3, 5}, {1, 3, 5}, {2, 3, 5}, {1, 2, 3, 5}, {4, 5}, {1, 4, 5}, {2, 4 , 5} , {1, 2, 4, 5} , {3, 4, 5} , {1, 3, 4, 5} , {2, 3, 4, 5} , {1, 2, 3, 4 , 5}}

Somit kommen wir zu allen 32 Teilmengen von {1, 2, 3, 4, 5}.