我們如何遞歸地尋找集合的所有分區？

找出集合的所有分區

在數學中，集合的分區是不相交子集（區塊或單元）的集合，其union 是原始集合。尋找集合的所有分區是一個經典的組合問題，在許多領域都有應用。

遞歸解決方案

遞歸解決方案可以有效解決這個問題。該演算法首先產生給定集合的所有可能的兩部分分區。對於每個兩部分分區，第二部分進一步分為兩部分，產生三個部分分區。此過程遞歸地繼續，直到找到所有分區。

實作

這是遞歸演算法的C# 實作：

using System;
using System.Collections.Generic;
using System.Linq;

namespace Partitioning {
    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());
            }
        }
    }
}

說明

說明

說明

Allarts>方法採用輸入集元素並產生所有可能的分區。它首先呼叫 GetTuplePartitions 來產生子集元素的所有兩部分分區。對於每個兩部分分區，它遞歸呼叫 GetAllPartitions。此遞歸過程持續進行，直到找到所有分區。

GetTuplePartitions 方法產生集合中所有可能的兩部分分區。它透過迭代所有可能的位元模式（即二進制數）來實現此目的，這些位元模式表示將元素分配給兩個分區。

{ {1}, {2}, {3} }
{ {1, 2}, {3} }
{ {1, 3}, {2} }
{ {1}, {2, 3} }
{ {1, 2, 3} }

範例對於集合{1 , 2, 3}，GetAllPartitions 方法將產生下列分區：This演算法有效地產生集合的所有分區，使其成為各種應用中的有價值的工具，例如組合優化和數據分析。

以上是我們如何遞歸地尋找集合的所有分區？的詳細內容。更多資訊請關注PHP中文網其他相關文章！