<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\section{Das Paket sets}\label{sets}

Wie schon in der Einleitung beschrieben ist sets dazu konzipiert, Mengenoperationen zu unterstÃ¼tzen. Die Elemente einer Menge sind normalerweise einfacher Text, Sie kÃ¶nnen aber auch Kommandos in Mengen einfÃ¼gen. Diese werden -- auÃŸer
bei der Ausgabe -- nicht ausgepackt. Die Verwendung von geschweiften Klammern in Mengen funktioniert leider nicht. In diesem Fall mÃ¼ssen Sie sich eine AbkÃ¼rzung definieren, die ohne Parameter auskommt. Parameter ohne Klammern funktionieren jedoch. "`\verb|H"agar|"' wÃ¤re also ein gÃ¼ltiges Element einer Menge. Die Elemente "`\verb|\endset|"' und "`\verb|\empty|"' dÃ¼rfen nicht in einer Menge enthalten sein.

Da ein Dokument nur wenige Autoren hat, wurde auf Effizienz kein besonderer Wert gelegt. Die Mengen sollten deshalb relativ klein sein. Sollten Sie dennoch eine Menge mit hunderten oder gar tausenden von Elementen anlegen wollen, kann es passieren, dass der Stack von \TeX\ Ã¼berlÃ¤uft.

Normalerweise ist bei einer Menge die Reihenfolge der Elemente egal. Dies ist auch hier bei den meisten Befehlen der Fall. Bei Abweichungen wird darauf hingewiesen.

Das Paket sets benÃ¶tigt \LaTeXe.

\subsection{Verwendung}\label{sets-verwendung}

In diesem Unterabschnitt soll die Verwendung des Pakets sets vorgestellt werden. Dabei werden einige Beispielmengen verwendet werden:
\begin{eqnarray*}
	A &amp;=&amp; \{Alice, Bob, Charly\}\\
	B &amp;=&amp; \{Alice, Bob\}\\
	C &amp;=&amp; \{Bob, Dean\}\\
	D &amp;=&amp; \{Dean\}\\
	L &amp;=&amp; \emptyset
\end{eqnarray*}

%-----------------------------------------------------------------------------
\subsubsection{Konstruktoren}\label{konstruktoren}
Um eine Menge anzulegen, gibt es die Befehle\\
\mbox{}\hspace{2em}\verb$\newset{&lt;Menge&gt;}{&lt;Inhalt&gt;}$\\
und\\
\mbox{}\hspace{2em}\verb$\newsetsimple{&lt;Menge&gt;}{&lt;Inhalt&gt;}$.\\
\texttt{&lt;Menge&gt;} ist ein Kommandoname, unter dem die Menge spÃ¤ter erreichbar sein soll. Die Elemente einer Menge werden durch \texttt{|} getrennt. Die Menge $A$ lieÃŸe sich also wie folgt definieren:\\
\mbox{}\hspace{2em}\verb$\newset{\mA}{Alice|Bob|Charly}$\\
Die Menge $L$ wird mit\\
\mbox{}\hspace{2em}\verb$\newset{\mL}{}$\\
definiert.

\verb$\newset$ legt also eine neue Menge an. Diese wird dabei alphabetisch sortiert und Duplikate werden entfernt. Es wÃ¤re also egal gewesen, wenn bei der Definition von $A$ nach "`Charly"' ein weiteres Mal "`Alice"' gestanden hÃ¤tte.

Der Aufwand fÃ¼r Sortierung und Duplikatentfernung ist an dieser Stelle unnÃ¶tig. Will man diese Schritte nicht durchfÃ¼hren lassen, kann man eine Menge auch mit \verb$\newsetsimple$ definieren.

Da sie spÃ¤ter noch benÃ¶tigt werden, werden wir nun alle oben genannten Mengen anlegen:\\
\mbox{}\hspace{2em}\verb$\newsetsimple{\mA}{Alice|Bob|Charly}$ \newsetsimple{\mA}{Alice|Bob|Charly}\\
\mbox{}\hspace{2em}\verb$\newsetsimple{\mD}{Alice|Bob}$ \newsetsimple{\mB}{Alice|Bob}\\
\mbox{}\hspace{2em}\verb$\newsetsimple{\mC}{Bob|Dean}$ \newsetsimple{\mC}{Bob|Dean}\\
\mbox{}\hspace{2em}\verb$\newsetsimple{\mD}{Dean}$ \newsetsimple{\mD}{Dean}\\
\mbox{}\hspace{2em}\verb$\newsetsimple{\mL}{}$ \newsetsimple{\mL}{}
%-----------------------------------------------------------------------------
\subsubsection{Inspektoren}\label{inspektoren}
Inspektoren dienen dazu, Eigenschaften von Mengen herauszufinden oder diese auszugeben.

\paragraph{Ausgabe:}Eine Menge lÃ¤sst sich Ã¼ber\\
\mbox{}\hspace{2em}\verb$\listset$\\
ausgeben. Die Elemente werden in der Reihenfolge, in der sie in der Menge stehen, ausgegeben. Als Trennzeichen zwischen den Elementen wird das Komma verwendet.

\verb$\listset{\mA}$ ergibt also folgende Ausgabe:\\
\centerline{\listset{\mA}}

Manchmal mÃ¶chte man die Elemente einer Menge vielleicht auf andere Art und Weise trennen, z.\,B. mit einem \texttt{\&amp;} zur Darstellung in einer Tabelle. Hier hilft einem die (temporÃ¤re) Umdefinition des Kommandos\\
\mbox{}\hspace{2em}\verb$\setseparator$\\
weiter. Normalerweise hat dieses Makro den Ersetzungstext `\verb*$,\ $'.

\paragraph{GrÃ¶ÃŸenbestimmung:} Der nÃ¤chste Inspektor hat die Syntax\\
\mbox{}\hspace{2em}\verb$\sizeofset{$$M$\verb$}\is{&lt;ZÃ¤hler&gt;}$\\
\texttt{&lt;ZÃ¤hler&gt;} ist dabei der Name eines \LaTeX-ZÃ¤hlers, in dem die Anzahl der Elemente der Menge $M$ gespeichert wird. Die Kommandosequenz\\
\mbox{}\hspace{2em}\verb$\newcounter{mycounter}$\newcounter{mycounter}\\
\mbox{}\hspace{2em}\verb$\sizeofset{\mB}\is{mycounter}$\sizeofset{\mB}\is{mycounter}\\
\mbox{}\hspace{2em}\verb$\arabic{mycounter}$\\
fÃ¼hrt zur Ausgabe: "`\arabic{mycounter}"'
Wird die GrÃ¶ÃŸe der Menge $L$ bestimmt, ist das Ergebnis \sizeofset{\mL}\is{mycounter}wie erwartet "`\arabic{mycounter}"'.

\paragraph{PrÃ¼fung auf Mitgliedschaft:}Mit dem Befehl\\
\mbox{}\hspace{2em}\verb$\iselementofset{$$e$\verb$}{$$M$\verb$}$\\
kann Ã¼berprÃ¼ft werden, ob $e \in M$ gilt. Der Aufwand ist $O(1)$, da alle Arbeit durch die Mustererkennung von \TeX\ Ã¼bernommen wird. Die Befehlssequenz\\
\mbox{}\hspace{2em}\verb$\if \iselementofset{Bob}{\mC}Ja\else Nein\fi$\\
wÃ¼rde zur Ausgabe "`\if \iselementofset{Bob}{\mC}Ja\else Nein\fi"' fÃ¼hren, der gleiche Test mit Menge $D$ zu "`\if \iselementofset{Bob}{\mD}Ja\else Nein\fi"'.

%-----------------------------------------------------------------------------
\subsubsection{Modifikatoren}\label{modifikatoren}

\paragraph{Mengenvereinigung:}Die Operation $R := M_1 \cup M_2$ wird durch den Befehl\\
\mbox{}\hspace{2em}\verb|\unionsets{|$M_1$\verb|}{|$M_2$\verb|}\to{|$R$\verb|}|\\
realisiert. Ein paar Beispiele sind in Tabelle \ref{tab:ops} aufgefÃ¼hrt. Das Ergebnis der Operation ist eine sortierte Menge ohne Duplikate, die die Elemente der Mengen $M_1$ und $M_2$ enthÃ¤lt.

\paragraph{Mengendifferenz:}Die Operation $R := M_1 - M_2$ (auch $R := M_1 \backslash M_2$ geschrieben) lÃ¤sst sich mit dem Befehl\\
\mbox{}\hspace{2em}\verb|\minussets{|$M_1$\verb|}\minus{|$M_2$\verb|}\to{|$R$\verb|}|\\
durchfÃ¼hren. Ist $M_1$ eine sortierte Menge, wird auch $R$ sortiert sein. EnthÃ¤lt $M_1$ Duplikate, enthÃ¤lt $R$ eventuell ebenfalls diese Duplikate. Tabelle \ref{tab:ops} enthÃ¤lt einige Beispiele fÃ¼r die Verwendung dieses Befehls.

Die Operation kann man umgangssprachlich wie folgt formulieren: PrÃ¼fe fÃ¼r jedes Element $e$ aus $M_1$, ob $e \in M_2$ gilt. Wenn nein, fÃ¼ge $e$ zu $R$ hinzu. Und genau so wurde es auch straight forward implementiert!

\paragraph{Mengendurchschnitt:} Die Operation $R := M_1 \cap M_2$ wird durch den Befehl\\
\mbox{}\hspace{2em}\verb|\intersectsets{|$M_1$\verb|}{|$M_2$\verb|}\to{|$R$\verb|}|\\
ermÃ¶glicht. Auch hier gilt: Ist $M_1$ eine sortierte Menge, wird auch $R$ sortiert sein. EnthÃ¤lt $M_1$ Duplikate, enthÃ¤lt $R$ eventuell ebenfalls diese Duplikate.
Tabelle \ref{tab:ops} enthÃ¤lt auch Beispiele fÃ¼r die Verwendung dieser Operation.

Die Operation kann man umgangssprachlich wie folgt formulieren: PrÃ¼fe fÃ¼r jedes Element $e$ aus $M_1$, ob $e \in M_2$ gilt. Wenn ja, fÃ¼ge $e$ zu $R$ hinzu. Wenn man dies mit der Formulierung der Mengendifferenz vergleicht, fÃ¤llt auf, dass der einzige Unterschied im WÃ¶rtchen "`ja"' besteht. In der Implementierung drÃ¼ckt sich dies durch ein fehlendes \verb|\else| aus. Eigentlich verblÃ¼ffend einfach, wenn man bedenkt, dass formal $M_1 \cap M_2 \equiv M_1 \backslash (M_1\backslash M_2)$ gilt, was eine deutlich hÃ¶here KomplexitÃ¤t erwarten lÃ¤sst.

\begin{table}%[htb]
\begin{center}
\begin{tabular}{ll}\hline
\textbf{Befehl} &amp; \textbf{Ergebnis} \\ \hline 
\unionsets{\mA}{\mC}\to{\mR}\global\let\mR\mR
	\verb$\unionsets{\mA}{\mC}\to{\mR}$ &amp; "`\listset{\mR}"' \\ 
\unionsets{\mB}{\mD}\to{\mR}\global\let\mR\mR
	\verb$\unionsets{\mB}{\mD}\to{\mR}$ &amp; "`\listset{\mR}"' \\
\unionsets{\mL}{\mC}\to{\mR}\global\let\mR\mR
	\verb$\unionsets{\mL}{\mC}\to{\mR}$ &amp; "`\listset{\mR}"' \\
\unionsets{\mL}{\mL}\to{\mR}\global\let\mR\mR
	\verb$\unionsets{\mL}{\mL}\to{\mR}$ &amp; "`\listset{\mR}"' \\\hline
%
\minussets{\mA}\minus{\mC}\to{\mR}\global\let\mR\mR
	\verb$\minussets{\mA}\minus{\mC}\to{\mR}$ &amp; "`\listset{\mR}"' \\ 
\minussets{\mD}\minus{\mC}\to{\mR}\global\let\mR\mR
	\verb$\minussets{\mD}\minus{\mC}\to{\mR}$ &amp; "`\listset{\mR}"' \\
\minussets{\mD}\minus{\mB}\to{\mR}\global\let\mR\mR
	\verb$\minussets{\mD}\minus{\mB}\to{\mR}$ &amp; "`\listset{\mR}"' \\
\minussets{\mA}\minus{\mL}\to{\mR}\global\let\mR\mR
	\verb$\minussets{\mA}\minus{\mL}\to{\mR}$ &amp; "`\listset{\mR}"' \\\hline
%
\intersectsets{\mA}{\mB}\to{\mR}\global\let\mR\mR
	\verb$\intersectsets{\mA}{\mB}\to{\mR}$ &amp; "`\listset{\mR}"' \\ 
\intersectsets{\mC}{\mB}\to{\mR}\global\let\mR\mR
	\verb$\intersectsets{\mC}{\mB}\to{\mR}$ &amp; "`\listset{\mR}"' \\
\intersectsets{\mB}{\mD}\to{\mR}\global\let\mR\mR
	\verb$\intersectsets{\mB}{\mD}\to{\mR}$ &amp; "`\listset{\mR}"' \\
\intersectsets{\mA}{\mL}\to{\mR}\global\let\mR\mR
	\verb$\intersectsets{\mA}{\mL}\to{\mR}$ &amp; "`\listset{\mR}"' \\\hline
\end{tabular}
\caption{Mengenoperationen, Beispiele}
\label{tab:ops}
\end{center}
\end{table}

\paragraph{Sortieren:} Eine Menge $M$ kann alphabetisch sortiert werden. Dazu verwendet man den Befehl\\
\mbox{}\hspace{2em}\verb|\sortset{|$M$\verb|}{|$R$\verb|}|.\\
$R$ enthÃ¤lt danach die sortierte Menge. Die Sortierung erfolgt nach dem Sortierverfahren Bubblesort, einem Verfahren, das sich auch mit \TeX\ ohne grÃ¶ÃŸere Verrenkungen umsetzen lÃ¤sst.

Bei der Sortierung werden die Elemente so verglichen, wie Sie sie angegeben haben, d.\,h. eventuell enthaltene Kommandos werden nicht expandiert, sondern nach ihrem Namen verglichen (inklusive des Backslash).

\paragraph{Duplikatentfernung:} Diese Operation funktioniert \emph{nur} auf sortierten Mengen! Man benÃ¶tigt sie aber eigentlich auch kaum, da die Erstellung einer neuen Menge mit \verb|\newset| diese Aufgabe automatisch Ã¼bernimmt (indem sie dieses Makro verwendet). Ich habe mich aber dazu entschlossen, die Operation trotzdem verfÃ¼gbar zu machen; vielleicht benÃ¶tigt sie ja tatsÃ¤chlich einmal jemand.
Aufgerufen wird die Duplikateleminierung mit:\\
\mbox{}\hspace{2em}\verb|\deleteduplicates{|$M$\verb|}{|$R$\verb|}|,\\
wobei $R$ die Ergebnis-Menge darstellt und $M$ die sortierte Menge, deren Duplikate entfernt werden sollen.

%------------------------------------------------------------------------------
\subsection{AufwandsabschÃ¤tzung}
Tabelle \ref{tab:komplexitaet} beschreibt die KomplexitÃ¤t der Operationen in O-Notation. Dabei werden folgende Annahmen getroffen:
\begin{itemize}
  \item Die LÃ¤nge eines Elements einer Menge sei $m$.
  \item Die Anzahl der Elemente einer Menge sei $n$. Werden fÃ¼r eine Operation zwei Mengen benÃ¶tigt, gibt $n_1$ die KardinalitÃ¤t der ersten und $n_2$ die KardinalitÃ¤t der zweiten Menge an.
  \item Zur Vereinfachung sei der Aufwand fÃ¼r die Mustererkennung bei der ParameterÃ¼bergabe konstant.
\end{itemize}

Die angegebenen KomplexitÃ¤tsklassen kÃ¶nnen dazu dienen, eine Reihe von Mengenoperationen mÃ¶glichst gÃ¼nstig anzuordnen. Beispielsweise ist es besser, bei \verb@\intersectsets@ und \verb@\minussets@ als erste Menge die kleinere Menge zu Ã¼bergeben.

\begin{table}[htb]
  \begin{center}
  \begin{tabular}{lc}\hline
    \textbf{Operation} &amp; \textbf{KomplexitÃ¤tsklasse}\\ \hline
    Element-Vergleich &amp; $m$\\
    \verb@\sizeofset@ &amp; $n$\\
    \verb@\listset@ &amp; $n$\\
    \verb@\iselementofset@ &amp; $1$\\%\hline
    \verb@\sortset@ &amp; $m \cdot n^2$\\
    \verb@\deleteduplicates@ &amp; $n$\\%\hline
    \verb@\newset@ &amp; $m \cdot n^2$\\
    \verb@\newsetsimple@ &amp; $1$\\%\hline
    \verb@\unionsets@ &amp; $m \cdot (n_1 + n_2)^2$\\
    \verb@\intersectsets@ &amp; $n_1$\\
    \verb@\minussets@ &amp; $n_1$\\ \hline
  \end{tabular}
  \caption{KomplexitÃ¤tsklassen der Mengenoperationen}%
  \label{tab:komplexitaet}%
  \end{center}
\end{table}
</pre></body></html>