c# – 如何查找一个集合的所有分区

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

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

以下是C#中的一个实现.调用

Partitioning.GetAllPartitions(new[] { 1,3,4 })

产量

{ {1,4} },4},{4} },{3,{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());
            }
        }
    }
}