Potenzmenge mit Bedingung

I

illon

Gast
Hallo,

ich habe eine Liste mit Objekten und möchte die Potenzmenge dieser Liste bilden, mit Bestimmten Bedingungen. Es ist also nicht die gesamte Potenzmenge, sondern nur ein Teil davon. Aber am besten ein Beispiel:

Die Objekte können allersamt einer Klasse zugeordnet werden, es dürfen am Ende in einer Teilmenge, aber keine zwei Objekt mit derselben Klassifikation zugeordnet werden.
Die Ausgangsobjekt sind beispielsweise folgende:

A1,A2,B,C

A bezeichnet dabei die Klasse, 1 und 2 ist nur zum unterscheiden da.

Am Ende soll folgendes rauskommen:
Menge={{A1},{A2},{B},{C},{A1,B},{A1,C},{B,C},{A1,B,C},{A2,B,C}}

Ich hoffe ihr konntet verstehen was ich meine und kennt einen Weg dies effizient zu realisieren.
Danke
 

Marco13

Top Contributor
IMHO gibt's da zwei Möglichkeiten: Entweder, einfach ganz normal die Potenzmenge berechnen, und das Ergebnis danach filtern (also alles rauswerfen, was nicht rein soll) oder, wenn "viel" rausgefiltert werden muss, und das Erstellen der kompletten Potenzmenge dann Zeit- und Platzverschwendung wäre, schon während des Erstellens das Kreiterum überprüfen. Kannst mal bei den http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html das "PowerSetIterable" ansehen.
 
I

illon

Gast
Danke für deine schnelle Antwort. Ich denke, dass ein vorheriges filtern sinnvoll wäre.
Die Klasse habe ich mir angeguckt, leider verstehe ich nicht konkret wie diese mir weiterhelfen könnte, da dort auf Bitebene gearbeitet wird.
 

Marco13

Top Contributor
Hmja ... Bitebene... Man muss alle Kombinationen von Eingabeelementen finden - wie das mit der Binärdarstellung einer Zahl zusammenhängt, steht dort ja im Kommentar. Ganz konkret könnte man ja einfach sowas machen wie
Code:
String input[] = new String[]{ "A1", "A2", "B", "C" }
PowerSetIterable<String> psi = new PowerSetIterable<String>(input);

List<String[]> filteredPowerSet = new ArrayList<String[]>();
for (String s[] : psi)
{
    [b]if (containsNoTwoElementsFromSameClass(s))[/b]
    {
        filteredPowerSet.add(s);
    }
}
 
I

illon

Gast
Danke, das ist schon deutlich konkreter :). Aber eine Frage, was bedeuten die drei Punkte (T... input)? Ein Fehler? Was muss ich da einfügen?
Java:
public PermutationIterable(T... input)
    {
        this.input = input.clone();
        numPermutations = Combinatorics.factorial(input.length);
    }
 

Illuvatar

Top Contributor
Das sind sogenannte varargs. Im Endeffekt bedeutet die Zeile nichts anderes als
Java:
public PermutationIterable(T[] input)
Es hat nur den Vorteil, dass der Compiler zulassen würde es mit
Java:
new PermutationIterable<String>("foo", "bar", "foobar")
aufzurufen
 
I

illon

Gast
Freakig kurzer Code diese Klasse.
Vielen Dank für den Hinweis und die Erklärungen.
 
4

42

Gast
Hy!
Ich habe ein ganz ähnliches anliegen, jedoch in anderen Dimensionen. Ich muss auch eine bedingte Potenzmenge erstellen, jedoch handelt es sich um etwa 100 Elemente. Funktioniert dies halbwegs schnell oder geht das nicht? Ist die angeführte Klasse noch optimierbar?
 

XHelp

Top Contributor
Bist du sicher, dass du ca 10^30 (kommt auf die Bedingung an) Elemente gespeichert halten musst? Ansosnten: probier es doch einfach mal aus...
 
4

42

Gast
Es läuft gerade, aber dauert wohl etwas. Ich habe mal den Profiler angeschmissen und eine Frage:
In einem Array sind die verschiedenen Objekte vorhanden und es wird überprüft ob eine Klasse doppelt vertreten ist. Wenn dies der Fall ist, soll false zurück gegeben werden. Diese Operation ist laut Profiler ziemlich teuer. Meine Idee war folgende: Speichere die Klassifikation in einem Set und überprüfe ob die Klasse bereits vorkommt.
Java:
public static boolean checkClass(PowerHandler[] ph) {
        HashSet l1 = new HashSet();
        for (int i = 0; i < ph.length; i++) {
            if (l1.contains(ph[i].getClassific())) {
                return true;
            } else {
                l1.add(ph[i].getClassific());
            }
        }
        return false;
    }
Wie kann ich die Dinge optimaler gestalten? Eine Sortierung lohnt sich imho nicht oder doch? Der Comparator würde nur zwei Integer-Werte vergleichen. Die durchschnittliche Größe der Arrays müsste man theoretisch ausrechnen können und dann sagen ob es sich lohnt?!?
 
4

42

Gast
Danke.
Ich habe den boolean-Wert jetzt direkt ausgewertet und in meiner Testmenge 1 Sekunde gespart. Kleinvieh macht auch Mist, aber so dauert die Berechnung zurzeit einfach zu lange.
 
4

42

Gast
Ich nehme quasi folgenden Code:
Java:
String input[] = new String[]{ "A1", "A2", "B", "C" }
PowerSetIterable<String> psi = new PowerSetIterable<String>(input);

List<String[]> filteredPowerSet = new ArrayList<String[]>();
for (String s[] : psi)
{
    if (containsNoTwoElementsFromSameClass(s))
    {
        filteredPowerSet.add(s);
    }
}
angepasst auf meine Objekte. Die Funktion containsNoTwoElementsFromSameClass ist die eben angeführte. Die Objekte geben dabei einen int-Value zurück. Ich habe zurzeit 29 Objekte (wobei es insgesamt 10 Klassen gibt) und die Berechnung bzw. Generierung dauert mindestens Minuten, aber zuende laufen lassen habe ich das Ding noch nicht. Dazu dauert es zu lange. Bei 29 Objekten dürfte es doch maximal 536.870.912 Schleifendurchläufe geben, oder? Müsste doch noch machbar sein :D.
 

XHelp

Top Contributor
Da scheinst du ja was falsch angepasst zu haben. Vllt ist es in deinem Fall nicht alle generieren und dann filtern, sondern gleich richtige generieren.
 
4

42

Gast
Java brauch zurzeit etwa gute 5 Minuten.
Was macht eigentlich PowerSetIterable mit den Objekten? Werden diese referenziert oder eine Kopie angelegt? Kann ich eventuell in PowerSetIterable direkt eine Überprüfung einbauen damit die gar nicht erst generiert werden oder ist dies nicht lohnenswert? Die Klasse PowerSetIterable ist für mich ein Rätsel von wahnsinnigem Code. Ich habe den angeführten Code eigentlich nur kopiert und meine Klassennamen angepasst, von daher denke ich weniger, dass dort ein Fehler ist.
 
4

42

Gast
Java benötigt nur für den Schleifendurchlauf ohne irgendetwas zu machen bereits knappe 2 Minuten.
Java:
for (String s[] : psi)
{
}
 

Marco13

Top Contributor
Das liegt daran, dass Java so langsam ist. Ist ja eine interpretierte Sprache. Wenn es schnell sein muss, musst du es mit C machen.

:joke:

Beschreib' dein Problem nochmal genau und einigermaßen formal. Entweder, du hast den falschen Algorithmus, oder du kommst eben um die exponentielle Laufzeit nicht drumrum, und dann kommt's auf ein paar Milliarden Jahre mehr oder weniger auch nicht mehr an ;)
 
4

42

Gast
Also, der User kann bestimmte, ich sag mal "Blöcke" bzw. Objekte, spezifizieren. Diese dürfen nach einigen Regeln miteinander kombiniert werden. Dazu benötige ich die Potenzmenge mit Bedingungen. Anschließend stellt der Nutzer eine Anfrage, welche durch die verschiedenen Objekte unterschiedlich gut erfüllt wird. Es gibt eine Klasse die die Potenzmenge nach dieser Erfüllung bewertet. Der Nutzer bekommt dann die zulässige Kombination zurück, welches die Anfrage am besten erfüllt. Ich kann aber nicht einfach mit einem Block anfangen und dann bewerten, da ich ansonsten bei einem lokalen Maxima hängen bleiben würde. Deswegen brauche ich vorher die Potenzmenge.
 

XHelp

Top Contributor
Irgendwie ist die Zusammung von deiner Beschreibung folgende: "Ich mach irgendwas irgendwie, dann ist der Benutzer dran, dann mach ich wieder irgendwas und TADA"
 
4

42

Gast
Vielleicht kann man es am besten mit einem Gebäude erklären. Der Nutzer gibt vorher in Konfigurationsdateien an, welche Bauteile ihm zur Verfügung stehen. Diese dürfen auf bestimmte Weise kombiniert werden. Der Nutzer sagt dann später er möchte ein Stadion bauen und mein Programm liefert dann vielleicht kein Stadion, aber ein halbes wenn es die Bauteile halt nicht hergeben.
 

Marco13

Top Contributor
Nichts gegen Abstraktion aber... Wenn man den kürzesten Weg von Hamburg nach München finden will, muss man nicht ALLE möglichen Wege durchsehen, und schauen, welches der kürzeste ist.

Und das Beispiel ist bewußt gewählt: Es klingt ein bißchen nach einem Kürzeste-Wege-Problem. In jedem Fall ist es aber ein Optimierungsproblem. Und es wäre schon seltsam, wenn man dafür alle Kombinationen bräuchte.
 
4

42

Gast
Straßen besitzen einen unterschiedlichen Nutzen zum vorankommen und da gibt es wunderbare Abstraktionsebenen. Ich weiß aber schon was du meinst. Ich möchte aber zurzeit noch keine Heuristiken anwenden, da ich nicht bei einem lokalen Maximum hängen bleiben möchte (und jede Gruppe prinzipiell denselben Beitrag leisten kann). Falls es aber absolut von der Laufzeit nicht möglich ist, werde ich darauf zurückgreifen.
Da aber die Laufzeit bei 30 Elementen viel zu groß ist (und es leider exponentiell ist) werde ich mir etwas überlegen müssen.
 

Marco13

Top Contributor
Hm. Es würde vielleicht schon helfen, wenn du beschreiben würdest, wie z.B. die Bewertungsfunktion aussieht. Aber es könnte natürlich auch sein, dass es keine effiziente Lösung gibt. Wer weiß das schon.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
O Potenzmenge (Rekursion?) Java Basics - Anfänger-Themen 9
T if-else Bedingung wird ignoriert Java Basics - Anfänger-Themen 4
B Alle Strings bis zu einer Maimallänge aufzählen, die Bedingung erfüllen Java Basics - Anfänger-Themen 13
Lion.King if-Bedingung Java Basics - Anfänger-Themen 3
B Zuweisungen und Methodenaufrufe in Bedingung der while Schleife? Java Basics - Anfänger-Themen 2
Avalon Warum funktioniert eine Bedingung und eine andere nicht? Java Basics - Anfänger-Themen 2
L while Schleife mit 2 Bedingung endet nicht Java Basics - Anfänger-Themen 3
M Wie lassen sich Konstanten in Bedingung stellen? Java Basics - Anfänger-Themen 1
M Wie lassen sich Objektkonstanten initialisieren, wenn sie eine Bedingung erreichen? Java Basics - Anfänger-Themen 6
M Wie verknüpfe ich eine Bedingung mit einer Methode ohne if-Verzweigung & Bedingungsoperator? Java Basics - Anfänger-Themen 2
A Dividieren mit Bedingung? Java Basics - Anfänger-Themen 7
P Bedingung in Schleife wird nicht ausgeführt Java Basics - Anfänger-Themen 5
Dimax Collections groupingBy mit Bedingung Java Basics - Anfänger-Themen 11
H Frage zur if-Bedingung bzw switch case Java Basics - Anfänger-Themen 6
F Bedingung für Eingabe Java Basics - Anfänger-Themen 2
scratchy1 Variablen vertauschen wenn Bedingung "umgedreht" wird Java Basics - Anfänger-Themen 40
Hanschyo If Bedingung Fehler Java Basics - Anfänger-Themen 7
T Komischer Fehler mit einer if-Bedingung Java Basics - Anfänger-Themen 3
W while Schleife und Bedingung Java Basics - Anfänger-Themen 11
E if-Bedingung mit mehreren Möglichkeiten ? Java Basics - Anfänger-Themen 6
S DefaultTableCellRenderer mit Bedingung Java Basics - Anfänger-Themen 1
J Fehler abfangen mit einer Bedingung Java Basics - Anfänger-Themen 3
Z Verschachtelte If-Bedingung Java Basics - Anfänger-Themen 6
N Methode mit While-Schleife und If-Bedingung und Array-Initialisierung Java Basics - Anfänger-Themen 4
L (Integer) Liste nach aufsteigender Summe der Ziffern sortieren (mit Bedingung) Java Basics - Anfänger-Themen 8
I Welche Schleife/Bedingung nehme ich her Java Basics - Anfänger-Themen 5
C Compiler-Fehler Wird eine if Bedingung nach einer for-Schleife nach jeder Iteration überprüft? Java Basics - Anfänger-Themen 1
B Kann mir jemand diese Bedingung erklären Java Basics - Anfänger-Themen 5
L Methoden if Bedingung trotz Erfüllung, nicht angesprochen Java Basics - Anfänger-Themen 12
P Compiler-Fehler if Bedingung fehlerhaft Java Basics - Anfänger-Themen 7
X Schleife bis "Bedingung" ausführen Java Basics - Anfänger-Themen 13
TheMenox Verschachtelte If Bedingung Java Basics - Anfänger-Themen 4
M Erste Schritte if-Bedingung schlägt fehl Java Basics - Anfänger-Themen 4
T Eigene Bedingung in IF-Bedingung Java Basics - Anfänger-Themen 22
Ocram Variablen Vereinfachung einer Bedingung Java Basics - Anfänger-Themen 18
J Can't find symbol - Erstellung eines Objekts in if-Bedingung Java Basics - Anfänger-Themen 3
M Frage zu if-Bedingung Java Basics - Anfänger-Themen 1
F Erste Schritte If Bedingung in Schleife dynamisch erweitern Java Basics - Anfänger-Themen 4
J Wo liegt nur an dieser einfachen Bedingung mein Fehler? Java Basics - Anfänger-Themen 8
R for-Schleife bei erfüllter Bedingung beenden Java Basics - Anfänger-Themen 7
R if funktion ohne else - Bedingung trifft nicht zu, ausgabe nicht nachvollziehbar Java Basics - Anfänger-Themen 7
S if bedingung - Stunde und Minute vergleichen Java Basics - Anfänger-Themen 5
K If-Bedingung mit Wertzuweisung Java Basics - Anfänger-Themen 2
J Vererbung If-Bedingung im Konstruktor Java Basics - Anfänger-Themen 15
J Arrays prüfen und über if Bedingung ausgeben Java Basics - Anfänger-Themen 15
T if Bedingung Java Basics - Anfänger-Themen 16
MiMa for Schleife Bedingung Java Basics - Anfänger-Themen 4
M in jTable schreiben unter Bedingung Java Basics - Anfänger-Themen 3
J Erste Schritte Kurze Frage zu Listenern und If-Bedingung Java Basics - Anfänger-Themen 2
N Verifikation einer if-Bedingung Java Basics - Anfänger-Themen 9
P Variablen ArrayList mit Bedingung iterieren Java Basics - Anfänger-Themen 2
E if(Bedingung) Java Basics - Anfänger-Themen 9
L Erste Schritte Sollte ich hier lieber Cases verwenden oder wäre eine If-Bedingung besser? Java Basics - Anfänger-Themen 6
Anfänger2011 Wie bricht man alles ab wenn eine Bedingung nicht erfüllt ist? Java Basics - Anfänger-Themen 21
P Variablen Variable in if Bedingung anlegen, Wert zuweisen und diesen als Bedingung nutzen Java Basics - Anfänger-Themen 4
M Und Bedingung Java Basics - Anfänger-Themen 17
N Bedingung für Datentypen Java Basics - Anfänger-Themen 3
E if-Bedingung funktioniert nicht Java Basics - Anfänger-Themen 9
W Funktionsaufruf nach Bedingung Java Basics - Anfänger-Themen 3
S for schleife mit if bedingung Java Basics - Anfänger-Themen 21
S return(Bedingung) ? [mehrere Befehle] Java Basics - Anfänger-Themen 5
2 Bedingung bei Schleife Java Basics - Anfänger-Themen 23
E Methode in der Bedingung Java Basics - Anfänger-Themen 11
E if Bedingung Java Basics - Anfänger-Themen 4
H Sortierung eines String[][] mit Bedingung Java Basics - Anfänger-Themen 7
H Bedingung while-Schleife | integer number too large Java Basics - Anfänger-Themen 2
J Gibt es eine möglichkeit ähnlich wie .equals(bedingung1 ||bedingung ..n) ? Java Basics - Anfänger-Themen 5
S If-Bedingung Java Basics - Anfänger-Themen 15
P Einfache Bedingung (?) in Java Java Basics - Anfänger-Themen 3
K Fragen zu If-Bedingung Java Basics - Anfänger-Themen 3
S bedingung in variable speichern? Java Basics - Anfänger-Themen 8
neurox Ergebnis der if-Bedingung weiter verwenden Java Basics - Anfänger-Themen 5
G If-Schleife läuft ohne erfüllte Bedingung Java Basics - Anfänger-Themen 13
K Logik in if-Bedingung Java Basics - Anfänger-Themen 2
S if anweisung wird ausgeführt egal ob bedingung true o. false Java Basics - Anfänger-Themen 2
S For Schleife, Bedingung Java Basics - Anfänger-Themen 4
S Wildcard-Bedingung Java Basics - Anfänger-Themen 10
G Probleme mit break hier; in if-Bedingung Java Basics - Anfänger-Themen 5
M Schleife abhängig von Bedingung Java Basics - Anfänger-Themen 5
G while Bedingung? Java Basics - Anfänger-Themen 6
L Bedingung immer false, auch wenn zwei Strings gleich sind Java Basics - Anfänger-Themen 11
L IF Bedingung in SELECT Statement? Java Basics - Anfänger-Themen 3
M Kleine Frage zu If-Bedingung Java Basics - Anfänger-Themen 4
Bierhumpen String Bedingung. Java Basics - Anfänger-Themen 8
M Comparable - Bedingung erzwingen Java Basics - Anfänger-Themen 3
R Klassen nach Bedingung laden Java Basics - Anfänger-Themen 22
G Compiler sieht die Bedingung nicht! Java Basics - Anfänger-Themen 5
W if Bedingung mit "Außer" Java Basics - Anfänger-Themen 4

Ähnliche Java Themen

Neue Themen


Oben