我有一组不同的值。我正在寻找一种生成该集合的所有划分的方法，即将集合划分为子集的所有可能方式。
例如，集合{1、2、3}具有以下划分：
{ {1}, {2}, {3} },
{ {1, 2}, {3} },
{ {1, 3}, {2} },
{ {1}, {2, 3} },
{ {1, 2, 3} }.
{1, 2}，{3}与{3}，{2, 1}是相同的，不应作为单独的结果。Partitioning.GetAllPartitions(new[] { 1, 2, 3, 4 })
{ {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());
}
}
}
}
例如，一个包含3个元素的集合可以被划分为：
1）集合大小为1：{{1,2,3}, } <-- f(3,1)
2）集合大小为2：{{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}} <-- f(3,2)
3）集合大小为3：{{1}, {2}, {3}} <-- f(3,3)
现在让我们来计算f(4,2)：
有两种方法可以得到f(4,2)：
A. 向f(3,1)添加一个集合，这将从{{1,2,3}, }转换为{{1,2,3}, {4}}
B. 将4添加到f(3,2)的任何一个集合中，这将从
{{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}}
转换为
{{1,2,4},{3}}, {{1,2},{3,4}}
{{1,3,4},{2}}, {{1,3},{2,4}}
{{2,3,4},{1}}, {{2,3},{1,4}}
因此，f(4,2) = f(3,1) + f(3,2)*2
这导致f(n,m) = f(n-1,m-1) + f(n-1,m)*m
以下是获取所有集合划分的Java代码：
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;
}
}
结果如下：
[[[1, 2, 3]]]
[[[1, 3], [2]], [[1], [2, 3]], [[1, 2], [3]]]
[[[1], [2], [3]]]
分区数量：5
仅供娱乐，以下是更短的纯迭代版本:
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;
}
}
以下是需要翻译的内容：
这里进行测试：https://ideone.com/EccB5n
还有一个更简单的递归版本：
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);
}
}
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
（我不是在为 Ruby 宣传，只是想到这个解决方案可能更容易让一些读者理解。）
class Program
{
static void Main(string[] args)
{
var items = new List<Char>() { '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<IList<IList<T>>> Partitions<T>(this IList<T> items)
{
if (items.Count() == 0)
yield break;
var currentPartition = new int[items.Count()];
do
{
var groups = new List<T>[currentPartition.Max() + 1];
for (int i = 0; i < currentPartition.Length; ++i)
{
int groupIndex = currentPartition[i];
if (groups[groupIndex] == null)
groups[groupIndex] = new List<T>();
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<int>();
foreach (var item in currentPartition)
{
uniqueSymbolsSeen.Add(item);
if (uniqueSymbolsSeen.Count <= item)
return false;
}
return true;
}
}
我用于一个N成员集合的技巧。 1. 计算2^N 2. 将1到N之间的每个数字写成二进制数。 3. 您将得到2^N个二进制数，每个长度为N，每个数字告诉您如何将该集合分成子集A和B。如果第k位是0，则将第k个元素放入集合A中，否则将其放入集合B中。
{ {1}, {2}, {3} }。 - nitsas我已经在Matlab中实现了Donald Knuth非常棒的算法H，该算法列出所有分区。
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 < n
a(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
def allPossiblePartitions(l): # l is the list whose possible partitions have to be found
# to get all possible partitions, we consider the binary values from 0 to 2**len(l))//2-1
"""
{123} --> 000 (0)
{12} {3} --> 001 (1)
{1} {2} {3} --> 010 (2)
{1} {23} --> 011 (3) --> (0 to (2**3//2)-1)
iterate over each possible partitions,
if there are partitions>=days and
if that particular partition contains
more than one element then take max of all elements under that partition
ex: if the partition is {1} {23} then we take 1+3
"""
for i in range(0,(2**len(l))//2):
s = bin(i).replace('0b',"")
s = '0'*(len(l)-len(s)) + s
sublist = []
prev = s[0]
partitions = []
k = 0
for i in s:
if (i == prev):
partitions.append(l[k])
k+=1
else:
sublist.append(partitions)
partitions = [l[k]]
k+=1
prev = i
sublist.append(partitions)
print(sublist)