セットのすべてのパーティションを再帰的に見つけるにはどうすればよいでしょうか?

セットのすべてのパーティションの検索

数学では、セットのパーティションは、互いに素なサブセット (ブロックまたはセル) のコレクションです。 Union はオリジナルのセットです。セットのすべてのパーティションを見つけることは、多くの分野のアプリケーションにおける古典的な組み合わせ問題です。

再帰的解決策

再帰的解決策は、この問題を効果的に解決できます。アルゴリズムは、指定されたセットの可能なすべての 2 部構成のパーティションを生成することから始まります。 2 部構成のパーティションごとに、2 番目の部分がさらに 2 つの部分に分割され、3 部構成のパーティションが生成されます。このプロセスは、すべてのパーティションが見つかるまで再帰的に続行されます。

実装

再帰アルゴリズムの 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());
            }
        }
    }
}

説明

GetAllPartitionsメソッドは入力セット要素を受け取り、可能なすべてのパーティションを生成します。まず GetTuplePartitions を呼び出して、サブセット要素の 2 部構成のパーティションをすべて生成します。 2 つの部分からなるパーティションごとに、GetAllPartitions を再帰的に呼び出します。この再帰的なプロセスは、すべてのパーティションが見つかるまで続きます。

GetTuplePartitions メソッドは、セットの可能なすべての 2 部構成のパーティションを生成します。これは、2 つのパーティションへの要素の割り当てを表すすべての可能なビット パターン (つまり、2 進数) を反復処理することによって行われます。

例

セット {1 の場合, 2, 3} の場合、GetAllPartitions メソッドは次のパーティションを生成します:

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

Thisアルゴリズムはセットのすべてのパーティションを効率的に生成するため、組み合わせ最適化やデータ分析などのさまざまなアプリケーションで貴重なツールになります。

以上がセットのすべてのパーティションを再帰的に見つけるにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。