Feststellen ob eine Menge in einer anderen vorkommt

[Benutzername]

Hallo Delphi-Praxis

Ich muss feststellen ob eine Menge in einer anderen Menge vorkommt. Also ob sich die Mengen in irgendeinerweise überlappen. Ich muss nur feststellen ob das der Fall ist, nicht unbedingt welcher Teil mit dem anderen überlappt.

Ich habe also z.B. eine Liste mit 100 Namen. In der ersten Menge habe ich die Namen von 20-50 ausgewählt (30 Namen), in der zweiten Menge habe ich die Namen 30-45 ausgewählt (15 Namen). Die zweite Menge kommt also vollständig in der ersten vor.

Genauso könnte ich aber in der zweiten Menge die Namen 25-35 auswählen (10 Namen). Dann würde es nur eine Überlappung von 5 Namen geben (die Namen 30-35).

Wie finde ich nun herraus ob es eine Überlappung gibt oder nicht? Ich könnte sämtliche Möglichkeiten durchgehen und überprüfen, ich hoffe jedoch es kennt jemand eine einfache Mathematische Lösung.

Danke schonmal!

[DeddyH]

Multipliziere beide Mengen. Wenn eine leere Menge dabei herauskommt, gibt es keine Überlappung.

[edit] Beispiel:

Delphi-Quellcode:

var s1, s2: set of Byte;
begin
  s1 := [1..5];
  s2 := [6..10];
  if (s1 * s2) <> [] then
    ShowMessage('Überlappung')
  else
    ShowMessage('Keine Überlappung');
  Include(s1,6);
  if (s1 * s2) <> [] then
    ShowMessage('Überlappung')
  else
    ShowMessage('Keine Überlappung');
  Exclude(s2,6);
  if (s1 * s2) <> [] then
    ShowMessage('Überlappung')
  else
    ShowMessage('Keine Überlappung');
end;

[/edit]

[s.h.a.r.k]

mal eine vielleicht dumme fragen, aber geht das bei set of nicht auch mit in, also wie folgt:

Delphi-Quellcode:

var
  menge1 : set of Integer;
  menge2 : set of Integer;
begin
  menge1 := [1, 2];
  menge2 := [1, 2, 3, 4];
if (menge1 in menge2) then
{ ... }

[DeddyH]

in geht nur mit einzelnen Elementen.

[alzaimar]

Es handelt sich bei der Problemstellung des Fragestellers doch nicht notwendigerweise um Mengen im Sinne des Datentyps 'Set' von Delphi, sondern eher um Listen. Also müsste man eine Routine schreiben, die prüft, ob zwei Listen irgendwelche gemeinsamen Elemente beinhalten.

Selbst wenn man die Frage nach den Namen über Delphi-Mengen ('Set') abbildet, stößt man bei mehr als 255 Namen an die Grenze, insofern ist die Lösung nicht allgemeingültig.

Ich würde hier zunächst vorschlagen, die Namen in Stringlisten zu halten und die Prüfung über die 'IndexOf'-Methode zu bewerkstelligen:

Delphi-Quellcode:

Function ContainsElements (slA, slB : TStringList) : Boolean;
Var
  i : Integer;

Begin
  For i:=0 to slA.Count-1 Do 
    if slB.indexOf (slA[i]) Then Begin
      Result := True;
      Exit;
    End;
  Result := False;
End;

Keine Frage: Eine kompakte aber nicht sonderlich effiziente Implementierung. Optimierungspotential: Listen sortieren und durch die kürzere der beiden Listen iterieren.

[jfheins]

@DeddH, s.h.a.r.k: Aber das wichtigste von allem ist, dass diese Lösungen total irrelevant sind, da er keine Mengen im Sinne eines Sets hat, sondern

Zitat:

Zitat von Benutzername

z.B. eine Liste mit 100 Namen.

Name = String und String geht nicht mit set of.

Du mussta also manuell überprüfen, ob es überschneidungen gibt.

Sofern deine beiden Listen unsortiert sind, musst du jedes Element der einen Menge gegen jedes der anderen prüfen (Kannst natürlich abbrechen, wenn due eine Übereinstimmung geunden hast.)
Aufwand: n mal m (n=Länge von A, m=Länge von B)

Wenn deine Listen sortiert sind, kannst du mit weniger Aufwand und entsprechend schneller prüfen. (Du kannst dann jedes Element aus (der kleineren) Liste A in Liste B suchen, und finden /nicht finden mit Binärer Suche)
Aufwand: n * log(m)

[Benutzername]

Danke für eure Antworten.

Menge1 und Menge2 kann in folgenden Konstellationen auftreten ("-" sind die einzelnen Einträge und "+" sind die ausgewählten Elemente).

Code:

Liste ----------

A     ---+++---- M1
      -+++++++-- M2

B     ---+++---- M1
      -++++----- M2

C     ---+++---- M1
      ----++++-- M2

D     ---+++---- M1
      ---+++---- M2

E     ---+++---- M1
      ++-------- M2

F     ---+++---- M1
      -------++- M2

G     ---+++---- M1
      ----+----- M2

Demnnach kann ich mit folgenden Überprüfungen feststellen, ob Überlappungen vorliegen (ist nur bsp Code).

Delphi-Quellcode:

  Result:= false;
  if M1.Index = M2.Index then
  begin
    // D
    Result:= true;
  end else begin
    if M2.Index < M1.Index then
    begin
      // A, B, E
      if (M2.Index + M2.Size) - 1 >= M1.Index then
      begin
        // A, B
        Result:= true;
      end;
      // E
    end else begin
      if M2.Index > M1.Index then
      begin
        // C, F
        if M2.Index <= (M1.Index + M1.Size) - 1 then
        begin
          // C
          Result:= true;
        end;
        // F
      end else begin
        // G
        Result:= true;
      end;
    end;
  end;

Gibt es noch eine einfachere Möglichkeit das zu überprüfen?
Decken meine Überprüfungen alle Kombinationen ab?

[Uwe Raabe]

Wenn ich das richtig verstehe, dann sind deine "Mengen" eigentlich nur Subranges. Dann ist eine überprüfung der jeweiligen Bereichsgrenzen wohl der geschickteste Ansatz.

Seien A und B die beiden Mengen, MinA, MinB die jeweils kleinsten Elemente der Mengen und analog MaxA, MaxB die größten. Dann überlappen sich die Mengen nicht, wenn ((MaxA < MinB) or (MaxB < MinA)) ist.

[sx2008]

Da gibt es doch was in der Code-Library: http://www.delphipraxis.net/internal...ct.php?t=23230

[alzaimar]

Zitat:

Zitat von jfheins

Name = String und String geht nicht mit set of.

Als Index (siehe Eingangspost) schon.

Zitat:

Zitat von Uwe Raabe

Wenn ich das richtig verstehe, dann sind deine "Mengen" eigentlich nur Subranges.

Das wäre zu speziell.

Zitat:

Zitat von sx2008

Da gibt es doch was in der Code-Library: http://www.delphipraxis.net/internal...ct.php?t=23230

:dp: