我有一組不同的值。我正在尋找一種方法來生成這個集合的所有分區，即將集合分成子集的所有可能的方法。如何查找集合的所有分區
例如，集{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的整數。這會創建每個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<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());
}
}
}
}
哇，很酷。你可以回答你自己的問題？我從來沒想過這點。 – drankin2112
請參閱Bell number，這裏是一個簡單的想法，這一問題：
考慮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，2，3}}，{{1}}， }}，{{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]]] Number of partitions: 5
這裏是一個非遞歸解決方案
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;
}
}
這裏是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.在二進制文件中寫入1到N之間的每個數字。 3.您將得到每個長度爲N的2^N個二進制數，每個數字告訴您如何將該組分解爲子集A和B.如果第k個數字爲0，則將第k個元素置於集合A中，否則把它放在集合B
小心，這隻能找到2分區，即集合的分區分成2個子集。在原始示例中，這會忽略「{{1}，{2}，{3}}」。 – nitsas
這與接受的答案相同。 –
只是爲了好玩，這裏有一個較短的純迭代版本：
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);
}
}
我已經實現了高德納的非常漂亮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 < 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
我不能說，我也碰到過這個問題，但和一些搜索也沒有提供足夠的答案，+1。乍一看，代碼看起來也不錯（絕對比我接觸到的任何東西都更接近這個意圖），來自我的+1。 –