Ich lerne für ein Interview und bin online auf diese Frage in der Kategorie "Mathematik" gestoßen.
Generiere die Potenzmenge der gegebenen Menge:
%Vor%Bitte ich möchte keine explizite Antwort. Ich möchte nur Klarstellungen und Hinweise, wie man dieses Problem angehen kann.
Ich habe den Power-Set-Algorithmus bei Google überprüft und verstehe immer noch nicht, wie ich dieses Problem angehen soll.
Auch könnte jemand wiederholen, was die Frage verlangt.
Danke.
Power set of a set A is the set of all of the subsets of A.
Nicht die freundlichste Definition der Welt, aber ein Beispiel hilft:
z. Für {1, 2} sind die Teilmengen: {}, {1}, {2}, {1, 2}
Somit ist die eingestellte Leistung {{}, {1}, {2}, {1, 2}}
Beobachten Sie zum Generieren der Potenzmenge, wie Sie eine Teilmenge erstellen: Sie gehen nacheinander zu jedem Element und behalten es entweder bei oder ignorieren es.
Lassen Sie diese Entscheidung durch ein Bit (1/0) angezeigt werden.
Um also {1} zu generieren, wählen Sie 1 und drop 2 (10).
Auf ähnliche Weise können Sie einen Bitvektor für alle Teilmengen schreiben:
Um es noch einmal zu wiederholen: Eine Teilmenge wird gebildet, indem einige oder alle Elemente der ursprünglichen Menge eingeschlossen werden. Um also eine Teilmenge zu erstellen, gehen Sie zu jedem Element und entscheiden dann, ob Sie es behalten oder löschen möchten. Dies bedeutet, dass Sie für jedes Element 2 Entscheidungen haben. Für eine Menge können Sie also 2^N verschiedene Entscheidungen treffen, die 2^N verschiedenen Untergruppen entsprechen.
Sehen Sie, ob Sie es von hier abholen können.
Erstellen Sie ein Power-Set von:
{"A", "B", "C"}.
Pseudocode:
%Vor%Algorithmus-Erklärung:
1) Initialisiere sets auf eine leere Menge: {} .
2) Wiederholen Sie jedes Objekt in {"A", "B", "C"}
3) Wiederhole jedes set in deinem sets .
3.1) Erstellen Sie einen neuen Satz, der eine Kopie von set ist.
3.2) Hängen Sie die item an die new set an.
3.3) Hängen Sie new set an sets an.
4) Fügen Sie das item zu Ihrem sets hinzu.
4) Die Iteration ist abgeschlossen. Füge den leeren Satz zu deinem resultSets hinzu.
Exemplarische Vorgehensweise:
Schauen wir uns den Inhalt von sets nach jeder Iteration an:
Iteration 1, item="A":
%Vor%Iteration 2, item="B":
%Vor%Iteration 3, item="C":
%Vor%Iteration abgeschlossen, füge leere Menge hinzu:
%Vor%Die Größe der Sets ist 2 ^ | set | = 2 ^ 3 = 8 was richtig ist.
Beispielimplementierung in Java:
%Vor% Eingabe: [A, B, C]
Ausgabe: [[A], [A, C], [A, B], [A, B, C], [B], [B, C], [C], []]
Potenzmenge ist nur für alle Untergruppen für die gegebene Menge gesetzt. Es enthält alle Teilmengen (mit leerer Menge). Es ist bekannt, dass es in dieser Menge 2 N -Elemente gibt, wobei N die Anzahl der Elemente in der ursprünglichen Menge ist.
Um Power Set zu erstellen, kann folgende Sache verwendet werden:
N Bits (für kleinere Zahlen fügen Sie führende Nullen hinzu). Jedes Bit entspricht, wenn das bestimmte Mengenelement in der aktuellen Teilmenge enthalten ist. Beispiel, 3 Zahlen: a , b , c
Nun, Sie müssen alle Teilmengen generieren. Für eine Menge von Größe n gibt es 2 n Untergruppen.
Ein Weg wäre, über die Zahlen von 0 bis 2 n -1 zu iterieren
und wandle jedes in eine Liste von Binärziffern um, wobei 0 bedeutet ausschließen
Dieses Element und 1 bedeutet, dass es eingeschlossen ist.
Ein anderer Weg wäre Rekursion, Teile und Herrsche.
Generieren aller Kombinationen eines Satzes (durch Einschließen oder Nicht-Hinzufügen eines Elements). mit einem Beispiel erklären: 3 Elemente in einem Set (oder einer Liste). Die mögliche Teilmenge ist:
%Vor%Das Ergebnis ist 2 ^ (Anzahl der Elemente in der Menge).
Als solche können wir alle Kombinationen von N Elementen (mit Python) wie folgt erzeugen:
%Vor%