C#에서 재귀적 접근 방식을 사용하여 세트의 모든 파티션을 효율적으로 생성하는 방법은 무엇입니까?

집합의 파티션 생성

집합을 파티션이라고 알려진 별개의 하위 집합으로 나누는 것은 일반적인 수학 연산입니다. 이 기사에서는 순서의 부적절함으로 인해 중복이 발생하지 않도록 보장하면서 세트를 분할하는 효율적인 방법에 대해 설명합니다.

재귀적 접근 방식

저희 솔루션은 재귀 전략을 활용합니다. 가장 간단한 시나리오부터 시작합니다. 정확히 두 부분으로 분할하는 것입니다. 각 요소를 비트(첫 번째 부분은 0, 두 번째 부분은 1)로 표현함으로써 첫 번째 요소를 첫 번째 부분에 일관되게 배치하여 중복 결과를 방지합니다.

다음으로, 재귀 함수에 대해 알아봅니다. 더 복잡한 파티션을 다룹니다. 이 함수는 원래 세트에서 작동하여 두 부분으로 구성된 파티션을 모두 찾습니다. 각 파티션의 두 번째 부분은 두 부분으로 재귀적으로 분할되어 세 부분으로 구성된 파티션이 생성됩니다. 이 프로세스는 전체 세트가 분할될 때까지 계속됩니다.

구현

다음은 분할 알고리즘의 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)
        {
            // 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(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} }.

위 내용은 C#에서 재귀적 접근 방식을 사용하여 세트의 모든 파티션을 효율적으로 생성하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!