c++.de :: Kleinste Untermenge

Unregistrierter

Hallo ich habe folgendes Problem (und das Metaproblem, wie dieses Problem heißt):

Sei M eine Menge aus Mengen und daraus suche ein eine möglichst kleine Teilmenge, dessen Mengen Teilmengen aller Mengen aus M sind. (Nein, die triviale Antwort N§=\{ \emptyset \}§, die leere Menge, zählt nicht)
Leider sind alle Mengen sind unsortiert.

Beispiel:

Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	Sei das Alphabet {A B C D} M = { {A B C D}, // 1. Element { B C D}, // 2. Element { B D}, // 3. Element {A B C }, // 4. Element {A B }, // 5. Element {A D} // 6. Element } Ausgabe soll sein: N = { {A B }, // Teilmenge von 1, 4, 5 { B D}, // Teilmenge von 1, 2, 3 {A D}, // Teilmenge von 1, 6 }

Wie löse ich das möglichst schnell?

Gibt es einen schnelleren Weg als zunächst alle Mengen aus M zu sortieren, eine Menge aus M mit den anderen in linearer Zeit zu vergleichen - Also O(n^3)?

Bashar Mitglied 00:15:59 18.06.2012 Titel:

Warum ist das eine Lösung und z.B. nicht { {A}, {D} }? Irgendwie versteh ich das Kriterium nicht.

Unregistrierter

Weil {A} und {D} nicht aus M sind.

camper Mitglied 00:53:20 18.06.2012 Titel:

{A B } ist keine Teilmenge von { B C D}
also nicht Teilmenge aller Mengen aus M

{A B C } ist Teilmenge von 1 und 4 aber nicht in N

Mir scheint, der Text passt nicht zum Beispiel. Das "möglichst kleine Teilmenge"-Kriterium müsste auch noch erläutert werden. Oder soll sich "möglichst klein" auf die Elemente von N und nicht N selbst beziehen?

Unregistrierter

camper schrieb:

Mir scheint, der Text passt nicht zum Beispiel. Das "möglichst kleine Teilmenge"-Kriterium müsste auch noch erläutert werden.

Stimmt kann sein, ist schwierig zu erklären. (Mindestens für mich) §\mathcal{N} \subset \mathcal{M}§ sein Mengen von Mengen:
Es geht darum, dass: §\forall m \in \mathcal{M}\ \exists n \in \mathcal{N}: n \subset m§. Dabei soll §|\mathcal{N}|§ minimal, aber nicht §\{ \emptyset \}§ sein.
Also wenn
§m_1, m_2 \in \mathcal{M},\ m_1 \subset m_2§ dann kann §m_2§ nicht mehr in §\mathcal{N}§ sein, da es eine echte Obermenge eines anderen Menge §m_1§ aus §\mathcal{M}§ ist.

camper schrieb:

Oder soll sich "möglichst klein" auf die Elemente von N und nicht N selbst beziehen?

"möglichst klein" werden die Mengen von §\mathcal{N}§ automatisch.

Bashar Mitglied 01:46:42 18.06.2012 Titel:

Du suchst also alle Minima (bezüglich der Inklusionsordnung) aus M. Ich glaub das Problem hab ich verstanden

camper Mitglied 02:12:24 18.06.2012 Titel:

Also ist gesucht die Menge N aller Elemente von M, die keine echte Teilmenge in M besitzen?
Damit lässt sich schon mal ein simpler Algorithmus formulieren:
vergleiche jedes Element von M mit jedem anderen und entferne es, falls das Vergleichselement eine echte Teilmenge ist. Die Menge, die übrigbleibt, ist die gesuchte Menge (funktioniert, da die Eigenschaft, Teilmenge zu sein, transitiv ist).
O(n^2) falls der Vergleich konstante Komplexität hat.

Unregistrierter

Zum Weitergoogeln hilft dir vielleicht dieser Artikel: http://de.wikipedia.org/w ....... _exakten_%C3%9Cberdeckung
Das ist nicht genau dein Problem, aber ein ganz ähnliches.

Jester Moderator 11:38:44 18.06.2012 Titel:

Ne, das ist ein viel viel schwierigeres Problem und hat damit erstmal wenig zu tun.

knivil Mitglied 12:02:09 18.06.2012 Titel:

Zitat:

Also O(n^3)?

Was repraesentiert das n?