如何找到集合的所有分区

本文介绍了如何找到集合的所有分区的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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} 具有以下分区:

For instance, the set {1, 2, 3} has the following partitions:

{ {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.

可以在 Wikipedia 上找到集分区的详细定义.

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 到 (2^(n-1))-1 的计数来分配剩余的 n-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()); } } } }