Potenzmenge berechnen

[Marco]

Ich sollte als Hausaufgabe ein Programm schreiben, ein Teil des Programms sollte die Potenzmenge berechnen können.

Den Wikipedia Eintrag habe ich natürlich gelesen und verstehe nun auch was die Potenzmenge ist.
Beispiel für die Menge {1,2,3,}
DIe Potenzmenge wäre hier {{}{1}{2}{3}{1,2}{1,3}{2,3}{123}}
{} steht für die leere Menge, die ist in jeder Potenzmenge enthalten.

Den Input den mein Programm erhält kann unendlich gross sein, also 1000 Zahlen sollten dann kein Problem darstellen für mein Programm.

Ich kann bisher nur die Anzahl Elemente in der Potenzmenge mit der Fakultät berechnen. Mehr habe ich bisher nicht und habe auch nicht wirklich eine Idee.

Könnte mir jemand auf irgendeine Weise helfen?

Achja, das Programm muss in Java geschrieben werden und ich denke, die Elemten speichere ich in einem Hashset. Im Hashset werden doppelte Einträge gleich selber wieder rausgelöscht. Aber das dürfte euch eigentlich nicht interessieren, vielleicht nur wenn gerade jemand Java könnte^^

 

[DeletedUser]

Hallo Marco, nochmal zum Verständnis. Du kannst also schon ausrechnen, wieviele Elemente die Menge enthält, willst aber noch einen Weg diese Menge zu erstellen? Also wenn der Input zum Bsp. {1,7,3} ist, dann soll daraus die Potenzmenge erstellt werden?

Das dürfte bei deinen angegebenen 1000 Zahlen ganzschön viel Speicherbedarf haben und auch die Rechenzeit dürfte nicht gerade gering sein. Ansich müßte das aber mit Schleifen ziemlich einfach realisierbar sein.

MfG Glasi

Edit: Wie berechnest du die Größe über die Fakultät? Eigentlich berechnet sie sich doch wie bei Wikipedia aufgeführt über |P(X)| = 2^(|X|)

Edit2: Fürs Kleblättle hab ich mal nen Rechtschreibfehler geändert

 

[Marco]

Ja ok das mit der Fakultät stimmt nicht, hatte unsere Mathelehrerin gesagt.


Naja Speicher ist eigentlich egal, ich denke es iwird bei 1000 Zahlen innerhalb weniger Sekunden erledigt sein.

Nur weiss ich nicht wie ich die Schleifen machen soll.

 

[DeletedUser359]

for-schleifen

 

[DeletedUser359]

gibts bei Java keine cheats?

Es gibt bei Java Klassen, die beinhalten meistens die Lösungen der gesuchten Programme/Probleme. Wenn du das als Cheaten bezeichnen würdest, dann gibt es bei Java Cheats

Nein jetzt mal B2T: Versuch es doch in eine Forschleife irgendwie eine Variable hereinzupacken, die bestimmt, dass es eine beschränkte Anzahl an Möglichkeiten gibt. Ich weiß nicht genau, wie ich es dir erklären soll, vielleicht krieg ich es noch hinne ^^

 

[DeletedUser]

Und Marco, hast dus schon? Wenn ja würde mich deine Lösung mal interessieren. Ansonsten überleg ich mir heut Abend mal was

Wäre es ok die Teilmengen als String abzuspeichern?

MfG Glasi

 

[Marco]

Bisher habe ich es leider noch nicht, muss es mir nochmals genauer angucken^^

Ja die Teilmengen in Strings abzuspeichern ginge auch, ist dann aber etwas umständlich um es auszulesen.

Und vor allem sollen wir mit dieser Übung die Collection-Klassen (Arrays, Sets, List etc.) kennenlernen - leider.

 

[DeletedUser]

Ok, mir fiel grad die Antwort wie Schuppen von den Augen Ich schreibs dir grad. Kann dir ja schon mal sagen, das Schlüsselwort ist Rekursion

Ich denke in ner Stunde dürfte der Quelltext hier zu finden sein.

MfG Glasi

 

[DeletedUser]

Oh Mann ist die Lösung einfach und ich kam nicht drauf.

Hab als Beispiel erstemal immer nur "Set" geschrieben, kannst dir dann irgendein Set aussuchen, da Set ja nur nen Interface ist. Musst dann halt dran denken, da immer "Set" entsprechend zu ersetzen

public void potenzmenge_erstellen (Set neue_Liste, Set zu_verarbeitende_Elemente)
{
it1 = neue_Liste.itereator();
it2 = zu_verarbeitende_Elemente.iterator();
if (it2.hasNext())
{
erstes_Element_der_zu_verarbeitenden_Elemente = it2.next();
}
else
{
neue_Liste.add(new Set()); //Die leere Menge hinzufügen
return;
}
while(it1.hasNext())
{
aktuelles_Item_neue_Liste = it1.next();
neu_hinzuzufuegen = new Set(aktuelles_Item_neue_Liste); //neues Set mit dem aktuellen Item als Grundlage
neu_hinzuzufuegen.add(erstes_Element_der_zu_verarbeitenden_Elemente);
neue_Liste.add(neu_hinzuzufuegen);
}
neue_Liste.add(erstes_Element_der_zu_verarbeitenden_Elemente);
zu_verarbeitende_Elemente.remove(erstes_Element_der_zu_verarbeitenden_Elemente);
if (it2.hasNext())
{
potenzmenge_erstellen(neue_Liste,zu_verarbeitende_Elemente);
}
else
{
neue_Liste.add(new Set()); //Die leere Menge hinzufügen (ist doppelt drin, quasi aus Sicherheitsgründen, um eventuelle Fehlerquellen zu minimieren)
return;
}
}

Der erste Funktionsuafruf muss dann so aussehen:

endgueltige_Liste = new Set();
potenzmenge_erstellen(endgueltige_Liste, new Set(hiervon_zu_erstellen));
endgueltige_Liste.add(hiervon_zu_erstellen); //noch die gesamte Menge hinzufügen

So, das wars. Ich denke, dass es richtig sein müßte, habs aber net ausprobiert. Bei Fragen einfach mal melden, hab ICQ, MSN, Skyp, TS, IRC ... dann kann ich die dir da gern beantworten.

MfG Glasi

 

[Deleted User - 14831]

So jetzt noch die graphische Darstellung bitte...^^
(Also der Graph, bei dem oben die leere, Menge steht und dann in jeder Reihe darunter alle Mengen mit jeweils einem Element mehr

Sei {A, B, C}

(1. {}
2. {A} {B} {C}
3. {BC} {AC} {AB}
4. {ABC}))

(Übrigens nette Spielerei am Graph: Wenn man den in der Mitte knickt (also zwischen Zeile 2 und 3 in unserem Fall), ergänzen sich die aufeinander zu liegen kommenden Mengen zur Ursprungsmenge)

 

[Marco]

Hallo nochmals und vielen Dank
Auch wenn ichs nicht so kapiert habe, es funktioniert.

Habe noch 2 andere Methoden gemacht (mithilfe des Internets darauf gekommen). Per Google findet man schnell etwas. Ich möchte es euch noch kurz aufzeigen, ist vielelicht auch interessant

Die Anzahl der Teilmengen in der Potenzmenge erhält man ja durch 2^n, wobei n für die Anzahl Elemente des Inputs, z.B. {a,b,c}, zählt. Hierbei wäre n = 3 und die Anzahl der Teilmengen demfall 8.

Ach, am besten ihr schauts euch selbst an wen ihr Interesse habt http://www.mathsisfun.com/sets/power-set.html
Es wird durch binäre Schreibweise gelöst...

 

[DeletedUser]

Wobei mir die Lösung mit dem binären net gefällt. Wenn man nun die Menge umsortiert, was bei einer Menge keinen Unetrschied macht, dann ergeben sich daraus andere "binäre" Zahlen. Also ich find meine Lösung schöner

Wie gesagt, wenn du Fragen dazu hast. Frag 4L3X wo ich mich immer im IRC aufhalte oder schreib mich einfach an, kann mit den bereits erwähnten Diensten dienen.

MfG Glasi