如何查找集合的所有分区

我有一套不同的价值观。 我正在寻找一种方法来生成该集合的所有分区,即将集合划分为子集的所有可能方式。

例如,集合{1, 2, 3}具有以下分区:

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

由于这些是数学意义上的集合,因此顺序无关紧要。 例如, {1, 2}, {3}{3}, {2, 1} ,不应该是单独的结果。

可以在Wikipedia上找到集合分区的完整定义。

我找到了一个简单的递归解决方案。

首先,让我们解决一个更简单的问题:如何找到由两部分组成的所有分区。 对于n元素集,我们可以计算从0到(2 ^ n)-1的int。 这将创建每个n位模式,每个位对应一个输入元素。 如果该位为0,则将元素放在第一部分中; 如果为1,则元素放在第二部分中。 这留下了一个问题:对于每个分区,我们将得到重复的结果,其中两个部分被交换。 为了解决这个问题,我们将始终将第一个元素放入第一部分。 然后,我们通过从0到(2 ^(n-1)) – 1的计数来仅分配剩余的n-1个元素。

现在我们可以将一个集合分成两部分,我们可以编写一个递归函数来解决问题的其余部分。 该函数从原始集开始,找到所有两部分分区。 对于这些分区中的每一个,它递归地找到将第二部分分成两部分的所有方法,从而产生所有三部分分区。 然后它将每个分区的最后一部分分开以生成所有四部分分区,依此类推。

以下是C#中的实现。 调用

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

这是一个非递归的解决方案

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

这是Ruby中的一个大约20行的解决方案:

 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做些什么,我只是认为这个解决方案可能更容易让一些读者理解。)

我用于一组N个成员的技巧。 1.计算2 ^ N 2.以二进制forms写出1和N之间的每个数字。 3.你将获得每个长度为N的2 ^ N个二进制数,每个数字告诉你如何将集合分成子集A和B.如果第k个数字为0,则将第k个元素放入集合A中,否则放入它在B组中。

请参考贝尔号 ,这里是对这个问题的简要考虑:
将f(n,m)视为将一组n元素划分为m个非空集。

例如,一组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

以下是获取set的所有分区的Java代码:

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

结果是:
[[[1, 2, 3]]] [[[1, 3], [2]], [[1], [2, 3]], [[1, 2], [3]]] [[[1], [2], [3]]] Number of partitions: 5

只是为了好玩,这是一个较短的纯粹迭代版本:

 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 

在此测试: https : //ideone.com/EccB5n

还有一个更简单的递归版本:

 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

我已经实现了Donald Knuth的非常好的Algorith H,它列出了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