2.8.2. Vereinigung, Schnitt und Differenz von Mengen

Lernziele

Die Methoden join(), intersect() und diff()

Wenden wir uns nun den Mengenoperationen Schnitt, Vereinigung, Differenz und symmetrische Differenz zu. Diese werden von der Klasse set ebenfalls unterstützt.

Abbildung 2.25. Die Mengenoperationen Schnitt, Vereinigung und symmetrische Differenz

Die Mengenoperationen Schnitt, Vereinigung und symmetrische Differenz

Schnitt (1), Vereinigung (2) und symmetrische Differenz (3) zweier Mengen A und B.


Stellen wir uns vor, wir betreiben eine große Heiratsvermittlungsagentur. Die allgemeine Isolation und Vereinsamung des modernen Menschen in der Informationsgesellschaft sichert uns einen großen Kundenstamm. Jedes Jahr kommen neue Kunden hinzu (weil ihre Bereitschaft, an der Bushaltestelle oder im Café einfach jemand Nettes anzusprechen, dank SMS immer weiter abnimmt), und manche melden sich ab (weil wir sie erfolgreich vermittelt haben oder weil sie vom anderen Geschlecht ganz einfach die Schnauze voll haben). In den Dateien Customers01.txt und Customers02.txt stehen die Kundennummern der Kunden am Ende des Jahres 2001 bzw. 2002.

Die Datei Customers01.txt sieht etwa so aus:

7174
1234
5557
8181
9999
2788
5696

Die Datei Customers02.txt dagegen so:

1234
8181
2788
5696
2335
8912

Wir wollen nun wissen, welche Kunden wir in beiden Jahren insgesamt hatten, welche Kunden wir sowohl im ersten, als auch im zweiten Jahr betreut haben, welche Kunden wir im Jahr 2002 neu hinzugewonnen haben bzw. welche wir verloren haben. Dazu müssen wir die Mengen der Kundennummern vereinigen, schneiden bzw. sie mengenmäßig voneinander subtrahieren. Dies leistet das folgende Programm.

Filename: SetOperations.C
LEDA-Benutzer ab Version 5.0: Beachten Sie, dass die Header-Dateien nun in Module (Unterverzeichnisse) partitioniert sind!
#include <LEDA/set.h>
#include <fstream>
#include <iostream>

using leda::set;
using std::ifstream;
using std::cout;
using std::endl;

int main()
{
  ifstream is01("Data/Customers01.txt");
  ifstream is02("Data/Customers02.txt");

  set<int> S, T;
  
  int customer_id;

  while(is01 >> customer_id) 
      T.insert(customer_id);

  while(is02 >> customer_id) 
      S.insert(customer_id);
  
  set<int> All_customers = S.join(T);

  set<int> Both_years_customers = S.intersect(T);

  set<int> New_customers = S.diff(T);

  set<int> Signedoff_customers = T.diff(S);

  cout << "Altogether we had the following customers:\n";   
  forall(customer_id, All_customers) 
    cout << customer_id << " ";  
  cout << endl;

  cout << "The following were customers in both years:\n";   
  forall(customer_id, Both_years_customers) 
    cout << customer_id << " ";  
  cout << endl;

  cout << "The following customers are new:\n";   
  forall(customer_id, New_customers) 
    cout << customer_id << " ";  
  cout << endl;

  cout << "The following customers have signed off:\n";   
  forall(customer_id, Signedoff_customers) 
    cout << customer_id << " ";  
  cout << endl;
}

Das Programm gibt folgendes aus:

Altogether we had the following customers:
1234 2335 2788 5557 5696 7174 8181 8912 9999
The following were customers in both years:
1234 2788 5696 8181
The following customers are new:
2335 8912
The following customers have signed off:
5557 7174 9999

Die Methode

S.join(T);

vereinigt zwei Mengen S und T und liefert die Vereinigungsmenge zurück.

Dagegen schneidet die Methode

S.intersect(T);

zwei Mengen S und T und liefert die Vereinigungsmenge zurück.

Die Methode

S.diff(T);

berechnet die Mengendifferenz zweier Mengen S und T, d. h. sie liefert eine Menge zurück, die aus allen Elementen besteht, die in S, aber nicht in T enthalten sind.

Darüber hinaus gibt es noch die Methode

S.symdiff(T);

Diese berechnet die symmetrische Differenz zweier Mengen liefert. Das ist die Menge all derjenigen Elemente beider Mengen, die nicht in der Schnittmenge enthalten sind.

Mit den überladenen Vergleichsoperatoren können zwei Mengen auf Gleichheit, Ungleichheit, echte bzw. unechte Inklusion getestet werden. So testet etwa der Ausdruck

S < T;

ob S eine echte Teilmenge von T ist.

Schließlich gibt es noch die Methoden size(), empty() und clear() mit derselben Bedeutung wie bei Stacks und Queues.

Implementierung und weitere Informationen

Die Klasse set ist durch randomisierte Suchbäume implementiert.

Die Operationen insert(), del() und member() benötigen Zeit O(log(n)), wenn in der Menge n Elemente enthalten sind. empty() und size() benötigen konstante Zeit, und clear() Zeit O(n). Sind S und T zwei Mengen mit n bzw. m Elementen, so benötigen S.join(T) und S.diff(T) Zeit O(m·log(n+m)), und S.intersect(T) benötigt Zeit O(n·log(n+m)).

Es gibt noch einige Operatoren der Klasse set, die wir nicht beschrieben haben. Diese sind auf der entsprechenden Manualseite beschrieben.




Imprint-Dataprotection