Kleinste Untermenge

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:

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

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

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

camper

{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?

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

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

camper

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.

Zum Weitergoogeln hilft dir vielleicht dieser Artikel: http://de.wikipedia.org/wiki/Problem_der_exakten_Überdeckung
Das ist nicht genau dein Problem, aber ein ganz ähnliches.

Jester

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

knivil

Also O(n^3)?

Was repraesentiert das n?