如何找到一组的所有分区 [英] How to find all partitions of a set
问题描述
我有一组不同的值。我要寻找一种方式来产生这组所有分区,划分成一套子集,即所有可能的方式。
I have a set of distinct values. I am looking for a way to generate all partitions of this set, i.e. all possible ways of dividing the set into subsets.
例如,集 {1,2,3}
有以下分区:
{ {1}, {2}, {3} },
{ {1, 2}, {3} },
{ {1, 3}, {2} },
{ {1}, {2, 3} },
{ {1, 2, 3} }.
由于这些是套在数学意义上,顺序是无关紧要的。例如, {1,2},{3}
是一样的 {3},{2,1}
并且不应该是一个单独的结果。
As these are sets in the mathematical sense, order is irrelevant. For instance, {1, 2}, {3}
is the same as {3}, {2, 1}
and should not be a separate result.
设置分区的详尽定义可以在维基百科被发现。
A thorough definition of set partitions can be found on Wikipedia.
推荐答案
我发现一个简单的递归解决方案。
I've found a straightforward recursive solution.
首先,让我们解决一个简单的问题:如何找到准确地由两部分组成的所有分区。对于n元素集合,我们可以指望从0到(2 ^ N)-1一个int。这产生每n位模式,每一个比特对应一个输入元件。如果该位是0,我们把在第一部分中的元件;如果它是1,该元件被放置在第二部分。这使得一个问题:对于每个分区,我们将得到一个重复的结果,其中两部分进行交换。为了解决这个问题,我们将始终把第一个元素到第一个部分。然后,我们只由从0计数到分发剩余的n-1个元素(2 ^(N-1)) - 1
First, let's solve a simpler problem: how to find all partitions consisting of exactly two parts. For an n-element set, we can count an int from 0 to (2^n)-1. This creates every n-bit pattern, with each bit corresponding to one input element. If the bit is 0, we place the element in the first part; if it is 1, the element is placed in the second part. This leaves one problem: For each partition, we'll get a duplicate result where the two parts are swapped. To remedy this, we'll always place the first element into the first part. We then only distribute the remaining n-1 elements by counting from 0 to (2^(n-1))-1.
现在,我们可以划分一组分成两个部分,我们可以写一个递归函数,解决这个问题的其余部分。该功能与原集开始了,发现所有两部分的分区。对于每个分区,它递归查找所有途径到第二部分分成两个部分,得到的所有三个部分组成的分区。然后,它把每个分区的最后一部分,以产生所有四个部分的分区,并依此类推。
Now that we can partition a set into two parts, we can write a recursive function that solves the rest of the problem. The function starts off with the original set and finds all two-part-partitions. For each of these partitions, it recursively finds all ways to partition the second part into two parts, yielding all three-part partitions. It then divides the last part of each of these partitions to generate all four-part partitions, and so on.
下面是在C#中的实现。呼叫
The following is an implementation in C#. Calling
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());
}
}
}
}
这篇关于如何找到一组的所有分区的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!