指定されたセットのすべてのセット パーティションを生成するにはどうすればよいでしょうか?

すべての集合パーティションの生成

組み合わせ数学における基本的な問題の 1 つは、指定された集合のすべてのパーティションを見つけることです。セット パーティションは、セットをブロックまたはパーツと呼ばれる、空ではない素のサブセットに分割します。

この問題では、個別の要素を持つセットのすべてのパーティションを列挙する方法を求めます。集合 {1, 2, 3} について考えてみましょう。そのパーティションは次のとおりです:

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

分割アルゴリズム

タスクは 2 つのサブ問題に分類できます: 2 つの部分への分割と 1 つの部分を複数への分割Parts.

2 部パーティション化

n 要素セットの場合、すべての 2 部パーティションは、各要素を n- 内のビットとして表すことによって生成できます。ビットパターン。 0 ビットは最初の部分への配置を示し、1 ビットは 2 番目の部分への配置を示します。パーツを交換するときに結果が重複するのを避けるために、常に最初の要素を最初のパーツに割り当てます。これにより、(2^(n-1))-1 個の固有の 2 部構成のパターンが残ります。

再帰的分割

2 部構成の分割手法を導入すると、次のようになります。すべてのパーティションを再帰的に構築できます。

1. 空の固定部分と元のセットから開始します。 suffix.
2. サフィックスの 2 つの部分からなるパーティションを生成します。
3. 各サフィックス パーティションについて、その 2 番目の部分を再帰的に複数の部分に分割します。
4. 固定部分と再帰部分を結合します。パーティションを作成して、固定部分を含むすべてのパーティションを取得します。
5. すべての要素が取得されるまで手順 4 を繰り返します。

C# 実装

次の C# 実装では、再帰的パーティショニング アルゴリズムが使用されています。

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) {
            // Trivial partition: fixed parts followed by all suffix elements as a single block
            yield return fixedParts.Concat(new[] { suffixElements }).ToArray();

            // Two-group-partitions of suffix elements and their recursive sub-partitions
            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) {
            if (elements.Length < 2) yield break;

            for (int pattern = 1; pattern < 1 << (elements.Length - 1); pattern++) {
                List<T>[] resultSets = {
                    new List<T> { elements[0] },
                    new List<T>() 
                };
                
                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());
            }
        }
    }
}

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