Menge aller Partitionen

01.01.2025, 20:13

Malcang

Menge aller Partitionen

Hallo und frohes neues Jahr zusammen smile

mich beschäftigt seit einiger Zeit die Frage, wie man wohl die Menge aller Partitionen algorithmisch bestimmt.
Nehmen wir die Menge $\begin{eqnarray*} A = \{ 1,2,3\} \end{eqnarray*}$ . Dann ist die Menge aller Partitionen
$\begin{eqnarray*} M = \{ \{ \{ 1\},\{ 2\},\{ 3\}\}, \{ \{1 \},\{ 2,3\}\}, \{ \{2 \},\{ 1,3\}\}, \{ \{3 \},\{ 1,2\}\}, \{ \{ 1,2,3\}\} \} \end{eqnarray*}$

Das habe ich nur der Übersicht halber so geschrieben. Ich erhalte also eine Menge mit 5 Elementen.
Diese Menge war nun nicht schwer zu bestimmen, aber für die Menge $\begin{eqnarray*} A=\{1,2,3,4\} \end{eqnarray*}$ habe ich das schon nicht mehr hinbekommen. Ich sehe ein, dass es sicher rekursiv geht, aber sowas zu sehen fällt mir ganz schwer.
Ich wollte gerne ein python-Skript dazu schreiben.

Könnt ihr mir auf die Sprünge helfen?

01.01.2025, 20:18

IfindU

Auf diesen Beitrag antworten »

Ich würde vorschlagen es so zu machen:

Die Potenzmenge von $\begin{eqnarray*} \{ 1,2,...,n \} \end{eqnarray*}$ , genannt $\begin{eqnarray*} P(n) \end{eqnarray*}$ ist $\begin{eqnarray*} P(n) = \{ A \cup \{n\} | A \in P(n-1)\} \cup \{ A | A \in P(n-1)\} =\{ A \cup \{n\} | A \in P(n-1)\} \cup P(n-1) \end{eqnarray*}$ .

D.h. nimm die vorige Potenzmenge und erstelle für jede Menge zwei neue Mengen: eine mit $\begin{eqnarray*} n \end{eqnarray*}$ und einmal ohne (d.h. die Originalmenge).

Edit: Ich sollte eher lesen statt antworten. Es ist hier nicht die Potenzmenge, aber man kann ähnlich vorgehen: Das neue Element muss eine eigene Menge sein oder Teil einer anderen Menge in einer Partition.

01.01.2025, 20:26

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Es ist hier nicht die Potenzmenge, aber man kann ähnlich vorgehen: Das neue Element muss eine eigene Menge sein oder Teil einer anderen Menge in einer Partition.

Ich glaube dass ist es, was meine Intuition gut beschreibt. Ich werde das mal damit für eine vierelementige enge versuchen.

Danke dir! smile

Neue Frage »

Antworten »

Menge aller Partitionen

Verwandte Themen