Cómo encontrar todas las particiones de un conjunto

Tengo un conjunto de valores distintos. Estoy buscando una forma de generar todas las particiones de este conjunto, es decir, todas las formas posibles de dividir el conjunto en subconjuntos.

Por ejemplo, el conjunto {1, 2, 3} tiene las siguientes particiones:

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

Como estos son conjuntos en el sentido matemático, el orden es irrelevante. Por ejemplo, {1, 2}, {3} es lo mismo que {3}, {2, 1} y no debe ser un resultado separado.

Una definición completa de las particiones establecidas se puede encontrar en Wikipedia .

He encontrado una solución recursiva directa.

Primero, resolvamos un problema más simple: cómo encontrar todas las particiones que constan de exactamente dos partes. Para un conjunto de n elementos, podemos contar un int de 0 a (2 ^ n) -1. Esto crea cada patrón de n bits, con cada bit correspondiente a un elemento de entrada. Si el bit es 0, colocamos el elemento en la primera parte; si es 1, el elemento se coloca en la segunda parte. Esto deja un problema: para cada partición, obtendremos un resultado duplicado donde las dos partes se intercambian. Para remediar esto, siempre colocaremos el primer elemento en la primera parte. A continuación, distribuimos los elementos n-1 restantes contando de 0 a (2 ^ (n-1)) – 1.

Ahora que podemos dividir un conjunto en dos partes, podemos escribir una función recursiva que resuelva el rest del problema. La función comienza con el conjunto original y encuentra todas las particiones de dos partes. Para cada una de estas particiones, encuentra de forma recursiva todas las formas de dividir la segunda parte en dos partes, produciendo todas las particiones de tres partes. Luego divide la última parte de cada una de estas particiones para generar todas las particiones de cuatro partes, y así sucesivamente.

La siguiente es una implementación en C #. Vocación

 Partitioning.GetAllPartitions(new[] { 1, 2, 3, 4 }) 

rendimientos

 { {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} }. 
 using System; using System.Collections.Generic; using System.Linq; namespace PartitionTest { public static class Partitioning { public static IEnumerable GetAllPartitions(T[] elements) { return GetAllPartitions(new T[][]{}, elements); } private static IEnumerable GetAllPartitions( 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 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> GetTuplePartitions( 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[] resultSets = { new List { elements[0] }, new List() }; // 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()); } } } } 

Aquí hay una solución no recursiva

 class Program { static void Main(string[] args) { var items = new List() { 'A', 'B', 'C', 'D', 'E' }; int i = 0; foreach (var partition in items.Partitions()) { Console.WriteLine(++i); foreach (var group in partition) { Console.WriteLine(string.Join(",", group)); } Console.WriteLine(); } Console.ReadLine(); } } public static class Partition { public static IEnumerable>> Partitions(this IList items) { if (items.Count() == 0) yield break; var currentPartition = new int[items.Count()]; do { var groups = new List[currentPartition.Max() + 1]; for (int i = 0; i < currentPartition.Length; ++i) { int groupIndex = currentPartition[i]; if (groups[groupIndex] == null) groups[groupIndex] = new List(); groups[groupIndex].Add(items[i]); } yield return groups; } while (NextPartition(currentPartition)); } private static bool NextPartition(int[] currentPartition) { int index = currentPartition.Length - 1; while (index >= 0) { ++currentPartition[index]; if (Valid(currentPartition)) return true; currentPartition[index--] = 0; } return false; } private static bool Valid(int[] currentPartition) { var uniqueSymbolsSeen = new HashSet(); foreach (var item in currentPartition) { uniqueSymbolsSeen.Add(item); if (uniqueSymbolsSeen.Count <= item) return false; } return true; } } 

Aquí hay una solución en Ruby de aproximadamente 20 líneas:

 def copy_2d_array(array) array.inject([]) {|array_copy, item| array_copy.push(item)} end # # each_partition(n) { |partition| block} # # Call the given block for each partition of {1 ... n} # Each partition is represented as an array of arrays. # partition[i] is an array indicating the membership of that partition. # def each_partition(n) if n == 1 # base case: There is only one partition of {1} yield [[1]] else # recursively generate the partitions of {1 ... n-1}. each_partition(n-1) do |partition| # adding {n} to a subset of partition generates # a new partition of {1 ... n} partition.each_index do |i| partition_copy = copy_2d_array(partition) partition_copy[i].push(n) yield (partition_copy) end # each_index # Also adding the set {n} to a partition of {1 ... n} # generates a new partition of {1 ... n} partition_copy = copy_2d_array(partition) partition_copy.push [n] yield(partition_copy) end # block for recursive call to each_partition end # else end # each_partition 

(No estoy tratando de engañar a Ruby, simplemente pensé que esta solución podría ser más fácil de entender para algunos lectores).

Un truco que utilicé para un conjunto de N miembros. 1. Calcule 2 ^ N 2. Escriba cada número entre 1 y N en binario. 3. Obtendrás 2 ^ N números binarios de longitud N y cada número te dice cómo dividir el conjunto en el subconjunto A y B. Si el dígito k’th es 0, coloca el elemento k’th en el conjunto A, de lo contrario, pon en el conjunto B.

Por favor, consulte el número de Bell , aquí hay una breve reflexión sobre este problema:
considere f (n, m) como partición un conjunto de n elemento en m conjuntos no vacíos.

Por ejemplo, la partición de un conjunto de 3 elementos puede ser:
1) establecer el tamaño 1: {{1,2,3},} <- f (3,1)
2) establecer el tamaño 2: {{1,2}, {3}}, {{1,3}, {2}}, {{2,3}, {1}} <- f (3,2)
3) establecer el tamaño 3: {{1}, {2}, {3}} <- f (3,3)

Ahora calculemos f (4,2):
hay dos formas de hacer f (4,2):

A. agregue un conjunto a f (3,1), que convertirá de {{1,2,3},} a {{1,2,3}, {4}}
B. agregue 4 a cualquiera de los conjuntos de f (3,2), que se convertirá de
{{1,2}, {3}}, {{1,3}, {2}}, {{2,3}, {1}}
a
{{1,2,4}, {3}}, {{1,2}, {3,4}}
{{1,3,4}, {2}}, {{1,3}, {2,4}}
{{2,3,4}, {1}}, {{2,3}, {1,4}}

Entonces f(4,2) = f(3,1) + f(3,2)*2
que resulta en f(n,m) = f(n-1,m-1) + f(n-1,m)*m

Aquí está el código de Java para obtener todas las particiones del conjunto:

 import java.util.ArrayList; import java.util.List; public class SetPartition { public static void main(String[] args) { List list = new ArrayList<>(); for(int i=1; i<=3; i++) { list.add(i); } int cnt = 0; for(int i=1; i<=list.size(); i++) { List>> ret = helper(list, i); cnt += ret.size(); System.out.println(ret); } System.out.println("Number of partitions: " + cnt); } // partition f(n, m) private static List>> helper(List ori, int m) { List>> ret = new ArrayList<>(); if(ori.size() < m || m < 1) return ret; if(m == 1) { List> partition = new ArrayList<>(); partition.add(new ArrayList<>(ori)); ret.add(partition); return ret; } // f(n-1, m) List>> prev1 = helper(ori.subList(0, ori.size() - 1), m); for(int i=0; i> l = new ArrayList<>(); for(List inner : prev1.get(i)) { l.add(new ArrayList<>(inner)); } l.get(j).add(ori.get(ori.size()-1)); ret.add(l); } } List set = new ArrayList<>(); set.add(ori.get(ori.size() - 1)); // f(n-1, m-1) List>> prev2 = helper(ori.subList(0, ori.size() - 1), m - 1); for(int i=0; i> l = new ArrayList<>(prev2.get(i)); l.add(set); ret.add(l); } return ret; } } 

Y el resultado es:
[[[1, 2, 3]]] [[[1, 3], [2]], [[1], [2, 3]], [[1, 2], [3]]] [[[1], [2], [3]]] Number of partitions: 5

Solo por diversión, aquí hay una versión más corta y puramente iterativa:

 public static IEnumerable>> GetAllPartitions(T[] elements) { var lists = new List>(); var indexes = new int[elements.Length]; lists.Add(new List()); lists[0].AddRange(elements); for (;;) { yield return lists; int i,index; for (i=indexes.Length-1;; --i) { if (i<=0) yield break; index = indexes[i]; lists[index].RemoveAt(lists[index].Count-1); if (lists[index].Count>0) break; lists.RemoveAt(index); } ++index; if (index >= lists.Count) lists.Add(new List()); for (;i 

Pruebe aquí: https://ideone.com/EccB5n

Y una versión recursiva más simple:

 public static IEnumerable>> GetAllPartitions(T[] elements, int maxlen) { if (maxlen<=0) { yield return new List>(); } else { T elem = elements[maxlen-1]; var shorter=GetAllPartitions(elements,maxlen-1); foreach (var part in shorter) { foreach (var list in part.ToArray()) { list.Add(elem); yield return part; list.RemoveAt(list.Count-1); } var newlist=new List(); newlist.Add(elem); part.Add(newlist); yield return part; part.RemoveAt(part.Count-1); } } 

https://ideone.com/Kdir4e

He implementado el muy agradable Algorith H de Donald Knuth que enumera todas las particiones en Matlab

https://uk.mathworks.com/matlabcentral/fileexchange/62775-allpartitions–s– http://www-cs-faculty.stanford.edu/~knuth/fasc3b.ps.gz

 function [ PI, RGS ] = AllPartitions( S ) %% check that we have at least two elements n = numel(S); if n < 2 error('Set must have two or more elements'); end %% Donald Knuth's Algorith H % restricted growth strings RGS = []; % H1 a = zeros(1,n); b = ones(1,n-1); m = 1; while true % H2 RGS(end+1,:) = a; while a(n) ~= m % H3 a(n) = a(n) + 1; RGS(end+1,:) = a; end % H4 j = n - 1; while a(j) == b(j) j = j - 1; end % H5 if j == 1 break; else a(j) = a(j) + 1; end % H6 m = b(j) + (a(j) == b (j)); j = j + 1; while j < na(j) = 0; b(j) = m; j = j + 1; end a(n) = 0; elementsd %% get partitions from the restricted growth stirngs PI = PartitionsFromRGS(S, RGS); end