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

セットの分割: 再帰的アプローチ

セットのすべての分割を見つけるタスクは、コンピュータ サイエンスと数学で頻繁に発生します。パーティションは、セットを素のサブセットに分割し、元のセットのすべての要素をまとめて含みます。

まず、セットを 2 つのサブセットに分割するという、より単純な問題を考えてみましょう。 n 要素セットの場合、バイナリ ビットマスクを使用してパーティションを表すことができます。各ビットはセットの要素に対応し、0 は最初のサブセットへの配置を示し、1 は 2 番目のサブセットへの配置を示します。これにより、各要素が 1 つのサブセットに確実に割り当てられるようになります。

最初のサブセット内の最初の要素の存在を処理するには、最初のビットが 0 であるビットマスクのみを考慮します。これにより、ビットマスクの数が 2 に減ります。 ^(n-1).

このアプローチを一般化するには、セットを再帰的に複数のサブセットに分割できます。 2 つの部分からなるすべてのパーティションから開始し、次に 2 番目のサブセットを 2 つの部分に分割し、次に 3 番目のサブセットというように分割します。この再帰的なプロセスにより、考えられるすべてのパーティションが生成されます。

指定された配列のすべてのパーティションを生成する C# での実装例を次に示します。

using System;
using System.Collections.Generic;

namespace Partitioning
{
    public static class Program
    {
        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 remaining elements as one block
            yield return fixedParts.Concat(new[] { suffixElements }).ToArray();

            // Get all two-part partitions of suffix elements and subdivide recursively
            var suffixPartitions = GetTuplePartitions(suffixElements);

            foreach (Tuple<T[], T[]> suffixPartition in suffixPartitions)
            {
                var recursivePartitions = GetAllPartitions(fixedParts.Concat(new[] { suffixPartition.Item1 }).ToArray(), suffixPartition.Item2);
                foreach (T[][] partition in recursivePartitions)
                {
                    yield return partition;
                }
            }
        }

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

要素の配列を指定して GetAllPartitions を呼び出すと、考えられるすべてのパーティションが生成されます。そのセットの場合。

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