如何查找集合中的所有分区

  • Z时代
  • 2024-01-10
  • 分类：问答

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

例如，集合{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元素集，我们可以将一个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());
            }
        }
    }
}

以上是 如何查找集合中的所有分区 的全部内容， 来源链接： utcz.com/qa/417521.html

回到顶部