Bagaimanakah Kami Boleh Mencari Semua Pembahagian Set secara Rekursif?

Mencari Semua Partition Set

Dalam matematik, partition set ialah himpunan subset terputus (blok atau sel) yang kesatuan adalah set asal. Mencari semua partition set ialah masalah gabungan klasik dengan aplikasi di banyak kawasan.

Penyelesaian Rekursif

Penyelesaian rekursif boleh menyelesaikan masalah ini dengan berkesan. Algoritma bermula dengan menjana semua partition dua bahagian yang mungkin bagi set yang diberikan. Bagi setiap partition dua bahagian, bahagian kedua dibahagikan lagi kepada dua bahagian, menghasilkan partition tiga bahagian. Proses ini diteruskan secara rekursif sehingga semua partition ditemui.

Pelaksanaan

Berikut ialah pelaksanaan C# bagi algoritma rekursif:

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

Penjelasan

Kaedah GetAllPartitions mengambil set input elemen dan menjana semua partition yang mungkin. Ia mula-mula memanggil GetTuplePartitions untuk menjana semua partition dua bahagian elemen subset. Untuk setiap partition dua bahagian, ia secara rekursif memanggil GetAllPartitions. Proses rekursif ini berterusan sehingga semua partition ditemui.

Kaedah GetTuplePartitions menjana semua partition dua bahagian yang mungkin bagi satu set. Ia melakukan ini dengan mengulangi semua corak bit yang mungkin (iaitu, nombor perduaan) yang mewakili penetapan elemen kepada dua partition.

Contoh

Untuk set {1 , 2, 3}, kaedah GetAllPartitions akan menjana partition berikut:

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

Algoritma ini dengan cekap menjana semua partition set, menjadikannya alat yang berharga dalam pelbagai aplikasi, seperti pengoptimuman gabungan dan analisis data.

Atas ialah kandungan terperinci Bagaimanakah Kami Boleh Mencari Semua Pembahagian Set secara Rekursif?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!