Comment générer efficacement toutes les partitions d'un ensemble à l'aide d'une approche récursive en C# ?

Génération de partitions d'un ensemble

La division d'un ensemble en sous-ensembles distincts, appelés partitions, est une opération mathématique courante. Cet article explore une méthode efficace pour partitionner un ensemble, garantissant qu'aucun doublon ne se produit en raison de la non-pertinence de l'ordre.

Approche récursive

Notre solution utilise une stratégie récursive, en commençant par le scénario le plus simple : le partitionnement en exactement deux parties. En représentant chaque élément comme un bit (0 pour la première partie et 1 pour la seconde), nous évitons les résultats en double en plaçant systématiquement le premier élément dans la première partie.

Ensuite, nous approfondissons la fonction récursive qui traite des partitions plus complexes. La fonction opère sur l'ensemble d'origine, trouvant toutes les partitions en deux parties. La deuxième partie de chaque partition est divisée de manière récursive en deux parties, ce qui donne des partitions en trois parties. Ce processus se poursuit jusqu'à ce que l'ensemble soit partitionné.

Implémentation

Vous trouverez ci-dessous une implémentation C# de l'algorithme de partitionnement :

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());
            }
        }
    }
}

Invocation du partitionnement .GetAllPartitions(new[] { 1, 2, 3, 4 }) génère ce qui suit partitions :

{ {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} }.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!