Comment pouvons-nous générer toutes les partitions d'un ensemble donné ?

Générer toutes les partitions d'ensemble

L'un des problèmes fondamentaux des mathématiques combinatoires est de trouver toutes les partitions d'un ensemble donné. Une partition d'ensemble divise l'ensemble en sous-ensembles disjoints non vides, appelés blocs ou parties.

Dans ce problème, nous recherchons une méthode pour énumérer toutes les partitions d'un ensemble avec des éléments distincts. Considérons l'ensemble {1, 2, 3}. Ses partitions sont :

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

Algorithme de partitionnement

La tâche peut être décomposée en deux sous-problèmes : le partitionnement en deux parties et le partitionnement d'une partie en plusieurs parties.

Partitionnement en deux parties

Pour un ensemble de n éléments, toutes les partitions en deux parties peuvent être générées en représentant chaque élément comme un bit dans un modèle de n bits. Un bit 0 indique un placement dans la première partie et un bit 1 indique un placement dans la deuxième partie. Pour éviter les résultats en double lors de l'échange de pièces, nous attribuons toujours le premier élément à la première pièce. Cela laisse (2^(n-1))-1 modèles uniques en deux parties.

Partitionnement récursif

Avec la technique de partitionnement en deux parties en place, nous peut construire de manière récursive toutes les partitions.

1. Commencez avec une partie fixe vide et l'ensemble d'origine comme suffixe.
2. Générez des partitions en deux parties du suffixe.
3. Pour chaque partition de suffixe, partitionnez récursivement sa deuxième partie en plusieurs parties.
4. Combinez les parties fixes avec les parties récursives. partitions pour obtenir toutes les partitions contenant les parties fixes.
5. Répétez l'étape 4 jusqu'à ce que tous les éléments soient partitionné.

Implémentation C#

L'implémentation C# suivante utilise l'algorithme de partitionnement récursif :

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

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!