Wie können wir alle Mengenpartitionen einer gegebenen Menge generieren?

Generieren aller Mengenpartitionen

Eines der grundlegenden Probleme in der kombinatorischen Mathematik besteht darin, alle Partitionen einer gegebenen Menge zu finden. Eine Mengenpartition unterteilt die Menge in nicht leere disjunkte Teilmengen, die als Blöcke oder Teile bezeichnet werden.

In diesem Problem suchen wir nach einer Methode, um alle Partitionen einer Menge mit unterschiedlichen Elementen aufzuzählen. Betrachten Sie die Menge {1, 2, 3}. Seine Partitionen sind:

• {{1}, {2}, {3}}
• {{1, 2}, {3}}
• { {1, 3}, {2}}
• {{1}, {2, 3}}
• {{1, 2, 3}}

Partitionierungsalgorithmus

Die Aufgabe kann in zwei Teilprobleme unterteilt werden: Partitionierung in zwei Teile und Partitionierung eines Teils in mehrere Teile.

Zweiteilige Partitionierung

Für ein n-Element Set können alle zweiteiligen Partitionen erzeugt werden, indem jedes Element als Bit in einem n-Bit-Muster dargestellt wird. Ein 0-Bit gibt die Platzierung im ersten Teil an, und ein 1-Bit gibt die Platzierung im zweiten Teil an. Um doppelte Ergebnisse beim Austauschen von Teilen zu vermeiden, weisen wir immer das erste Element dem ersten Teil zu. Dies hinterlässt (2^(n-1))-1 einzigartige zweiteilige Muster.

Rekursive Partitionierung

Mit der zweiteiligen Partitionierungstechnik haben wir kann alle Partitionen rekursiv konstruieren.

1. Beginnen Sie mit einem leeren festen Teil und dem Originalsatz als Suffix.
2. Erzeugen Sie zweiteilige Partitionen des Suffixes.
3. Partitionieren Sie für jede Suffixpartition den zweiten Teil rekursiv in mehrere Teile.
4. Kombinieren Sie die festen Teile mit den rekursiven Partitionen, um alle Partitionen zu erhalten, die die festen Teile enthalten.
5. Wiederholen Sie Schritt 4, bis alle Elemente vorhanden sind sind partitioniert.

C#-Implementierung

Die folgende C#-Implementierung verwendet den rekursiven Partitionierungsalgorithmus:

using System;
using System.Collections.Generic;
using System.Linq;

namespace PartitionTest {
    public static class Partitioning {
        public static IEnumerable<T[][]> GetAllPartitions<T>(T[] elements) {
            return GetAllPartitions(new T[][]{}, elements);
        }

        private static IEnumerable<T[][]> GetAllPartitions<T>(T[][] fixedParts, T[] suffixElements) {
            // Trivial partition: fixed parts followed by all suffix elements as a single block
            yield return fixedParts.Concat(new[] { suffixElements }).ToArray();

            // Two-group-partitions of suffix elements and their recursive sub-partitions
            var suffixPartitions = GetTuplePartitions(suffixElements);
            foreach (Tuple<T[], T[]> suffixPartition in suffixPartitions) {
                var subPartitions = GetAllPartitions(
                    fixedParts.Concat(new[] { suffixPartition.Item1 }).ToArray(),
                    suffixPartition.Item2);
                foreach (var subPartition in subPartitions) {
                    yield return subPartition;
                }
            }
        }

        private static IEnumerable<Tuple<T[], T[]>> GetTuplePartitions<T>(T[] elements) {
            if (elements.Length < 2) yield break;

            for (int pattern = 1; pattern < 1 << (elements.Length - 1); pattern++) {
                List<T>[] resultSets = {
                    new List<T> { elements[0] },
                    new List<T>() 
                };
                
                for (int index = 1; index < elements.Length; index++) {
                    resultSets[(pattern >> (index - 1)) & 1].Add(elements[index]);
                }

                yield return Tuple.Create(resultSets[0].ToArray(), resultSets[1].ToArray());
            }
        }
    }
}

Das obige ist der detaillierte Inhalt vonWie können wir alle Mengenpartitionen einer gegebenen Menge generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!