From 6b1e587424463b3965c55c5949812c78c965dd58 Mon Sep 17 00:00:00 2001 From: chai Date: Wed, 23 Jun 2021 18:26:05 +0800 Subject: *misc --- Assets/Algorithms/Recursion/Recursion.cs | 129 +++++++++++++------------ Assets/Algorithms/Searching/SearchingHelper.cs | 113 ++++++++++++++++++---- 2 files changed, 159 insertions(+), 83 deletions(-) (limited to 'Assets/Algorithms') diff --git a/Assets/Algorithms/Recursion/Recursion.cs b/Assets/Algorithms/Recursion/Recursion.cs index c704f8f..7bfb171 100644 --- a/Assets/Algorithms/Recursion/Recursion.cs +++ b/Assets/Algorithms/Recursion/Recursion.cs @@ -13,58 +13,55 @@ namespace AlgorithmCollection.Recursion #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) - DivideAndConquer( // + 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) => // adhoc 最小子任务处理 // + B(C) - { // + C(B) - temp.Add(dataList[div.left]); // + B (ACD) - List newCompose = new List(temp); // + C (ABD) - outPerms.Add(newCompose); // + D (ABC) - temp.RemoveAt(temp.Count - 1); - }, - (DivisionDescriptor div, out bool bAdhoc) => // 划分 - { - int left = div.left; // 包含第一个元素在内的范围 - int right = div.right; - int pivot = (int)div.userdata; // 第一个元素在范围内的索引 - DivisionDescriptor[] divisions; - int l = left; - if (pivot != -1) - { - temp.Add(dataList[pivot]); - Algorithms.Swap(ref dataList, pivot, left); - l = left + 1; - } - divisions = new DivisionDescriptor[right - l + 1]; - int j = 0; - for (int i = l; i <= right ; ++i) - { - divisions[j].left = l; - divisions[j].right = right; - divisions[j].userdata = (int)i; - j++; - } - bAdhoc = l == right; - return divisions; + List> outPerms = new List>(); // A B C D + List temp = new List(dataList.Count); // + A (BCD) + DNC( // + 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; }, - null, // 合并 - (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); - } + (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; } @@ -105,30 +102,30 @@ namespace AlgorithmCollection.Recursion } #endregion - #region 分治算法 + #region 分治 public delegate DivisionDescriptor Init(); - public delegate void AdHoc(DivisionDescriptor division); - public delegate DivisionDescriptor[] Divide(DivisionDescriptor division, out bool bAdhoc); + 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 DivideAndConquer(Init init, AdHoc adhoc, Divide divide, Merge merge = null, Postprocess postprocess = null) + public static void DNC(Init init, Divide divide, Solve solve, Postprocess postprocess = null, Merge merge = null) { DivisionDescriptor div = init(); - _DivideAndConquer(div, adhoc, divide, merge, postprocess); + _DivideAndConquer(div, solve, divide, merge, postprocess); } - private static void _DivideAndConquer(DivisionDescriptor div, AdHoc adhoc, Divide divide, Merge merge, Postprocess postprocess) + private static void _DivideAndConquer(DivisionDescriptor div, Solve solve, Divide divide, Merge merge, Postprocess postprocess) { - bool bAdhoc; - DivisionDescriptor[] division = divide(div, out bAdhoc); - if (!bAdhoc) + DivisionDescriptor[] division; + bool bUnit = divide(div, out division); + if (!bUnit) { for(int i = 0; i < division.Length; ++i) { - _DivideAndConquer(division[i], adhoc, divide, merge, postprocess); + _DivideAndConquer(division[i], solve, divide, merge, postprocess); postprocess?.Invoke(division[i]); } merge?.Invoke(division); @@ -137,12 +134,20 @@ namespace AlgorithmCollection.Recursion { for(int i = 0; i < division.Length; ++i) { - adhoc(division[i]); + solve(division[i]); } } } + #endregion + + #region 动态规划 + private static void DP() + { + + } #endregion + } } \ No newline at end of file diff --git a/Assets/Algorithms/Searching/SearchingHelper.cs b/Assets/Algorithms/Searching/SearchingHelper.cs index a36e653..191ff5e 100644 --- a/Assets/Algorithms/Searching/SearchingHelper.cs +++ b/Assets/Algorithms/Searching/SearchingHelper.cs @@ -34,7 +34,7 @@ namespace AlgorithmCollection.Searching public static int BinarySearch(List data, T value) where T : IComparable, IEquatable { int index = -1; - RecursionHelper.DivideAndConquer( + RecursionHelper.DNC( () => { DivisionDescriptor div = new DivisionDescriptor(); @@ -42,24 +42,16 @@ namespace AlgorithmCollection.Searching div.right = data.Count - 1; return div; }, - (DivisionDescriptor div) => - { - if (data[div.left].CompareTo(value) == 0) - { - index = div.left; - } - }, - (DivisionDescriptor div, out bool bAdhoc) => + (DivisionDescriptor div, out DivisionDescriptor[] division) => { int left = div.left; int right = div.right; - DivisionDescriptor[] division = new DivisionDescriptor[1]; + division = new DivisionDescriptor[1]; if(right <= left) { division[0].left = left; division[0].right = right; - bAdhoc = true; - return division; + return true; } int mid = (left + right) / 2; T midValue = data[mid]; @@ -77,13 +69,18 @@ namespace AlgorithmCollection.Searching { division[0].left = mid; division[0].right = mid; - bAdhoc = true; - return division; + return true; } - bAdhoc = false; - return division; - } - ); + return false; + }, + (DivisionDescriptor div) => + { + if (data[div.left].CompareTo(value) == 0) + { + index = div.left; + } + } + ); return index; } @@ -113,10 +110,84 @@ namespace AlgorithmCollection.Searching return min; } - - public static T Select_Random(IList data, bool descent = false) where T : IList, IComparable + // 找到第n大或者第n小，类比快速排序 + // O(n) + public static bool Select(IList data, int n, bool bMin, ref T findValue) where T : IComparable { - return default(T); + bool suc = false; + T v = default(T); + RecursionHelper.DNC( + ()=> + { + DivisionDescriptor div = new DivisionDescriptor(); + div.left = 0; + div.right = data.Count - 1; + div.userdata = n; + return div; + }, + (DivisionDescriptor division, out DivisionDescriptor[] div) => + { + div = new DivisionDescriptor[1]; + int left = division.left; + int right = division.right; + int remain = (int)division.userdata; + if(right <= left) + { + div[0].left = left; + div[0].right = right; + div[0].userdata = remain; + return true; + } + int l = left; + int r = right + 1; + T val = data[l]; + while (true) + { + while ((bMin && data[++l].CompareTo(val) <= 0 || !bMin && data[++l].CompareTo(val) >= 0) && l < right); + while ((bMin && data[--r].CompareTo(val) >= 0 || !bMin && data[--r].CompareTo(val) <= 0) && r > left); + if (l >= r) + break; + Algorithms.Swap(ref data, l, r); + } + Algorithms.Swap(ref data, left, r); + int count = r - left + 1; + if(count > remain) + { + div[0].left = left; + div[0].right = r - 1; + div[0].userdata = remain; + } + else if(count < remain) + { + div[0].left = r + 1; + div[0].right = right; + div[0].userdata = remain - count; + } + else + { + div[0].left = r; + div[0].right = r; + div[0].userdata = 0; + return true; + } + return false; + }, + (DivisionDescriptor division)=> + { + if((int)division.userdata == 0) + { + int i = division.left; + v = data[i]; + suc = true; + } + } + ); + if (suc) + { + findValue = v; + return true; + } + return false; } } -- cgit v1.1-26-g67d0