# Potenzmenge mit Bedingung



## illon (1. Mai 2010)

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 (1. Mai 2010)

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.


----------



## illon (1. Mai 2010)

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 (1. Mai 2010)

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

```
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);
    }
}
```


----------



## illon (1. Mai 2010)

Danke, das ist schon deutlich konkreter . Aber eine Frage, was bedeuten die drei Punkte (T... input)? Ein Fehler? Was muss ich da einfügen?

```
public PermutationIterable(T... input)
    {
        this.input = input.clone();
        numPermutations = Combinatorics.factorial(input.length);
    }
```


----------



## illon (1. Mai 2010)

Ich denke ich kann dort einfach mein Objekt in den Konstruktor einfügen?


----------



## Illuvatar (1. Mai 2010)

Das sind sogenannte varargs. Im Endeffekt bedeutet die Zeile nichts anderes als

```
public PermutationIterable(T[] input)
```
Es hat nur den Vorteil, dass der Compiler zulassen würde es mit

```
new PermutationIterable<String>("foo", "bar", "foobar")
```
aufzurufen


----------



## illon (2. Mai 2010)

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


----------



## 42 (24. Aug 2010)

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 (24. Aug 2010)

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


----------



## 42 (24. Aug 2010)

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.

```
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?!?


----------



## XHelp (24. Aug 2010)

Auszug aus HashSet JavaDcos:


> boolean add(E e)
> Adds the specified element to this set if it is not already present.


----------



## 42 (24. Aug 2010)

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.


----------



## XHelp (24. Aug 2010)

Welche Berechnung? Wie machst du die? Was ist die Bedingung?
Dann lässt sich vllt auch eine Alternative finden...


----------



## 42 (24. Aug 2010)

Ich nehme quasi folgenden 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)
{
    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 .


----------



## XHelp (24. Aug 2010)

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.


----------



## 42 (24. Aug 2010)

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.


----------



## 42 (24. Aug 2010)

Java benötigt nur für den Schleifendurchlauf ohne irgendetwas zu machen bereits knappe 2 Minuten.

```
for (String s[] : psi)
{
}
```


----------



## Marco13 (24. Aug 2010)

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


----------



## 42 (24. Aug 2010)

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 (24. Aug 2010)

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


----------



## 42 (24. Aug 2010)

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 (24. Aug 2010)

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.


----------



## 42 (24. Aug 2010)

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 (24. Aug 2010)

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.


----------

