Wie generiert man effizient alle Partitionen einer Menge mithilfe eines rekursiven Ansatzes in C#?

Erzeugen von Partitionen einer Menge

Die Aufteilung einer Menge in verschiedene Teilmengen, sogenannte Partitionen, ist eine gängige mathematische Operation. Dieser Artikel befasst sich mit einer effizienten Methode zur Partitionierung einer Menge, um sicherzustellen, dass aufgrund der Irrelevanz der Reihenfolge keine Duplikate entstehen.

Rekursiver Ansatz

Unsere Lösung verwendet eine rekursive Strategie. Beginnend mit dem einfachsten Szenario: der Aufteilung in genau zwei Teile. Indem wir jedes Element als Bit darstellen (0 für den ersten Teil und 1 für den zweiten), vermeiden wir doppelte Ergebnisse, indem wir das erste Element konsequent im ersten Teil platzieren.

Als nächstes beschäftigen wir uns mit der rekursiven Funktion that Behandelt komplexere Partitionen. Die Funktion arbeitet mit dem ursprünglichen Satz und findet alle zweiteiligen Partitionen. Der zweite Teil jeder Partition wird rekursiv in zwei Teile partitioniert, wodurch dreiteilige Partitionen entstehen. Dieser Vorgang wird fortgesetzt, bis der gesamte Satz partitioniert ist.

Implementierung

Unten ist eine C#-Implementierung des 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)
        {
            // A trivial partition consists of the fixed parts
            // followed by all suffix elements as one block
            yield return fixedParts.Concat(new[] { suffixElements }).ToArray();

            // Get all two-group-partitions of the suffix elements
            // and sub-divide them recursively
            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)
        {
            // No result if less than 2 elements
            if (elements.Length < 2) yield break;

            // Generate all 2-part partitions
            for (int pattern = 1; pattern < 1 << (elements.Length - 1); pattern++) {
                // Create the two result sets and
                // assign the first element to the first set
                List<T>[] resultSets = {
                    new List<T> { elements[0] }, new List<T>() };
                // Distribute the remaining elements
                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());
            }
        }
    }
}

Aufrufen der Partitionierung .GetAllPartitions(new[] { 1, 2, 3, 4 }) generiert Folgendes Partitionen:

{ {1, 2, 3, 4} },
{ {1, 3, 4}, {2} },
{ {1, 2, 4}, {3} },
{ {1, 4}, {2, 3} },
{ {1, 4}, {2}, {3} },
{ {1, 2, 3}, {4} },
{ {1, 3}, {2, 4} },
{ {1, 3}, {2}, {4} },
{ {1, 2}, {3, 4} },
{ {1, 2}, {3}, {4} },
{ {1}, {2, 3, 4} },
{ {1}, {2, 4}, {3} },
{ {1}, {2, 3}, {4} },
{ {1}, {2}, {3, 4} },
{ {1}, {2}, {3}, {4} }.

Das obige ist der detaillierte Inhalt vonWie generiert man effizient alle Partitionen einer Menge mithilfe eines rekursiven Ansatzes in C#?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!