Solución:
Encontré una solución recursiva sencilla.
Primero, resolvamos un problema más simple: cómo encontrar todas las particiones que constan exactamente de 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. Luego, solo distribuimos los n-1 elementos 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 resto del problema. La función comienza con el conjunto original y busca 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, lo que produce 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<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());
}
}
}
}
Consulte el número de Bell, aquí hay un breve pensamiento sobre este problema:
considere f (n, m) como partición de un conjunto de n elementos 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. agregar un conjunto af (3,1), que se convertirá de {{1,2,3},} a {{1,2,3}, {4}}
B. sumar 4 a cualquiera del conjunto de f (3,2), que se convertirá de
{{1,2}, {3}}, {{1,3}, {2}}, {{2,3}, {1}}
para
{{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 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<Integer> 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<List<List<Integer>>> 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<List<List<Integer>>> helper(List<Integer> ori, int m) {
List<List<List<Integer>>> ret = new ArrayList<>();
if(ori.size() < m || m < 1) return ret;
if(m == 1) {
List<List<Integer>> partition = new ArrayList<>();
partition.add(new ArrayList<>(ori));
ret.add(partition);
return ret;
}
// f(n-1, m)
List<List<List<Integer>>> prev1 = helper(ori.subList(0, ori.size() - 1), m);
for(int i=0; i<prev1.size(); i++) {
for(int j=0; j<prev1.get(i).size(); j++) {
// Deep copy from prev1.get(i) to l
List<List<Integer>> l = new ArrayList<>();
for(List<Integer> inner : prev1.get(i)) {
l.add(new ArrayList<>(inner));
}
l.get(j).add(ori.get(ori.size()-1));
ret.add(l);
}
}
List<Integer> set = new ArrayList<>();
set.add(ori.get(ori.size() - 1));
// f(n-1, m-1)
List<List<List<Integer>>> prev2 = helper(ori.subList(0, ori.size() - 1), m - 1);
for(int i=0; i<prev2.size(); i++) {
List<List<Integer>> 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 breve puramente iterativa:
public static IEnumerable<List<List<T>>> GetAllPartitions<T>(T[] elements) {
var lists = new List<List<T>>();
var indexes = new int[elements.Length];
lists.Add(new List<T>());
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<T>());
for (;i<indexes.Length;++i) {
indexes[i]=index;
lists[index].Add(elements[i]);
index=0;
}
}
Pruebe aquí: https: //ideone.com/EccB5n
Y una versión recursiva más simple:
public static IEnumerable<List<List<T>>> GetAllPartitions<T>(T[] elements, int maxlen) {
if (maxlen<=0) {
yield return new List<List<T>>();
}
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<T>();
newlist.Add(elem);
part.Add(newlist);
yield return part;
part.RemoveAt(part.Count-1);
}
}
https://ideone.com/Kdir4e