我有一组不同的价值观。我正在寻找一种生成该集合的所有分区的方法,即将集合划分为子集的所有可能方法。
例如,集合{1, 2, 3}具有以下分区:
{1, 2, 3}
{ {1}, {2}, {3} }, { {1, 2}, {3} }, { {1, 3}, {2} }, { {1}, {2, 3} }, { {1, 2, 3} }.
由于这些是数学意义上的集合,因此顺序无关紧要。例如,{1, 2}, {3}与相同{3}, {2, 1},不应作为单独的结果。
{1, 2}, {3}
{3}, {2, 1}
集合分区的详细定义可以在Wikipedia上找到。
我找到了一个简单的递归解决方案。
首先,让我们解决一个简单的问题:如何找到完全由两部分组成的所有分区。对于一个n元素集,我们可以将一个int从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()); } } } }