From 2749e059084b99737d79aadd92521023b0f65f56 Mon Sep 17 00:00:00 2001 From: chai Date: Thu, 24 Jun 2021 16:41:21 +0800 Subject: *dp --- Assets/Algorithms/Recursion/Recursion_DC.cs | 144 ++++++++++++++++++++++++++++ 1 file changed, 144 insertions(+) create mode 100644 Assets/Algorithms/Recursion/Recursion_DC.cs (limited to 'Assets/Algorithms/Recursion/Recursion_DC.cs') diff --git a/Assets/Algorithms/Recursion/Recursion_DC.cs b/Assets/Algorithms/Recursion/Recursion_DC.cs new file mode 100644 index 0000000..7dc873d --- /dev/null +++ b/Assets/Algorithms/Recursion/Recursion_DC.cs @@ -0,0 +1,144 @@ +using System; +using System.Collections; +using System.Collections.Generic; +using AlgorithmCollection; +using UnityEngine; + +// 分治算法 +namespace AlgorithmCollection.Recursion +{ + + public static partial class RecursionHelper + { + + #region 分治框架 + public delegate DivisionDescriptor Init(); + public delegate void Solve(DivisionDescriptor division); + public delegate bool Divide(DivisionDescriptor division, out DivisionDescriptor[] divs);//返回值代表是否达到最小问题阈值 + public delegate void Merge(DivisionDescriptor[] divisions); + public delegate void Postprocess(DivisionDescriptor div); + + // 分治算法框架 + public static void DC(Init init, Divide divide, Solve solve, Postprocess postprocess = null, Merge merge = null) + { + DivisionDescriptor div = init(); + _DivideAndConquer(div, solve, divide, merge, postprocess); + } + + // 处理单个任务 + private static void _DivideAndConquer(DivisionDescriptor div, Solve solve, Divide divide, Merge merge, Postprocess postprocess) + { + DivisionDescriptor[] division; + bool bUnit = divide(div, out division); + if (!bUnit) + { + for (int i = 0; i < division.Length; ++i) + { + _DivideAndConquer(division[i], solve, divide, merge, postprocess); + postprocess?.Invoke(division[i]); + } + merge?.Invoke(division); + } + else + { + for (int i = 0; i < division.Length; ++i) + { + solve(division[i]); + } + } + } + #endregion + + #region 全排列，返回数据的所有组合 + public static void Permutations(List dataList, ref List> perms) + { + List> outPerms = new List>(); // A B C D + List temp = new List(dataList.Count); // + A (BCD) + DC( // + B (CD) + () => // init // + C(D) + { // +D + DivisionDescriptor div = new DivisionDescriptor(); // + D(C) + div.userdata = -1; // +C + div.left = 0; // + C (BD) + div.right = dataList.Count - 1; // + B(D) + return div; // + D(B) + }, // + D (BC) + (DivisionDescriptor div, out DivisionDescriptor[] divs) => // 划分 // + B(C) + { // + C(B) + int left = div.left; // 包含第一个元素在内的范围 // + B (ACD) + int right = div.right; // + C (ABD) + int pivot = (int)div.userdata; // 第一个元素在范围内的索引 // + D (ABC) + int l = left; + if (pivot != -1) + { + temp.Add(dataList[pivot]); + Algorithms.Swap(ref dataList, pivot, left); + l = left + 1; + } + divs = new DivisionDescriptor[right - l + 1]; + int j = 0; + for (int i = l; i <= right; ++i) + { + divs[j].left = l; + divs[j].right = right; + divs[j].userdata = (int)i; + j++; + } + return l == right; + }, + (DivisionDescriptor div) => // solve 最小子任务处理 + { + temp.Add(dataList[div.left]); + List newCompose = new List(temp); + outPerms.Add(newCompose); + temp.RemoveAt(temp.Count - 1); + }, + (DivisionDescriptor div) => //子任务后处理 + { + int pivot = (int)div.userdata; // 第一个元素的索引 + int left = div.left; + int right = div.right; + Algorithms.Swap(ref dataList, pivot, left); + temp.RemoveAt(temp.Count - 1); + } + ); + perms = outPerms; + } + + // 生成器形式，每次返回一个组合 + public static IEnumerable Permutations(List data) + { + foreach (var perm in _Permutations(data, 0, data.Count - 1)) + { + yield return perm; + } + } + + // 计算start~end范围内的全排列 + private static IEnumerable _Permutations(List data, int start, int end, List perm = null) + { + if (perm == null) + perm = new List(data.Count); + if (start == end) + { + perm.Add(data[start]); + yield return perm; + perm.RemoveAt(perm.Count - 1); + } + else + { + for (int i = start; i <= end; ++i) + { + perm.Add(data[i]); + Algorithms.Swap(ref data, start, i); + IEnumerator itor = _Permutations(data, start + 1, end, perm).GetEnumerator(); + while (itor.MoveNext()) + yield return itor.Current; + Algorithms.Swap(ref data, start, i); + perm.RemoveAt(perm.Count - 1); + } + } + } + #endregion + } +} \ No newline at end of file -- cgit v1.1-26-g67d0