Bagaimana untuk Menjana Semua Pembahagian Set Dengan Cekap Menggunakan Pendekatan Rekursif dalam C#?

Menjana Pembahagian Set

Membahagikan set kepada subset yang berbeza, dikenali sebagai partition, ialah operasi matematik yang biasa. Artikel ini menyelidiki kaedah yang cekap untuk membahagikan set, memastikan tiada pendua timbul disebabkan oleh ketidakrelevanan susunan.

Pendekatan Rekursif

Penyelesaian kami menggunakan strategi rekursif, bermula dengan senario paling mudah: membahagikan kepada dua bahagian. Dengan mewakili setiap elemen sebagai sedikit (0 untuk bahagian pertama dan 1 untuk bahagian kedua), kami mengelakkan hasil pendua dengan meletakkan elemen pertama secara konsisten di bahagian pertama.

Seterusnya, kami menyelidiki fungsi rekursif yang menangani partition yang lebih kompleks. Fungsi ini beroperasi pada set asal, mencari semua partition dua bahagian. Bahagian kedua setiap partition dipisahkan secara rekursif kepada dua bahagian, menghasilkan partition tiga bahagian. Proses ini berterusan sehingga keseluruhan set dibahagikan.

Pelaksanaan

Di bawah ialah pelaksanaan C# bagi algoritma pembahagian:

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

Memajukan Pembahagian .GetAllPartitions(new[] { 1, 2, 3, 4 }) menjana yang berikut sekatan:

{ {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} }.

Atas ialah kandungan terperinci Bagaimana untuk Menjana Semua Pembahagian Set Dengan Cekap Menggunakan Pendekatan Rekursif dalam C#?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!