gpt4 book ai didi

c# - 如何找到集合的所有分区

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:13:57 26 4
gpt4 key购买 nike

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

例如,集合{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 元素集,我们可以从 0 到 (2^n)-1 计算一个整数。这将创建每个 n 位模式,每一位对应一个输入元素。如果该位为 0,我们将元素放在第一部分;如果为 1,则元素放在第二部分。这留下了一个问题:对于每个分区,我们将得到一个重复的结果,其中两个部分被交换。为了解决这个问题,我们总是将第一个元素放在第一部分中。然后我们只分配剩余的 n-1 个元素,从 0 到 (2^(n-1))-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());
}
}
}
}

关于c# - 如何找到集合的所有分区,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52769338/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com