dp

1 files changed, 1 insertions, 139 deletions

diff --git a/Assets/Algorithms/Recursion/Recursion.cs b/Assets/Algorithms/Recursion/Recursion.cs
index 7bfb171..6a223d0 100644
--- a/Assets/Algorithms/Recursion/Recursion.cs
+++ b/Assets/Algorithms/Recursion/Recursion.cs
@@ -8,146 +8,8 @@ using UnityEngine;
 namespace AlgorithmCollection.Recursion

 {

 

-    public static class RecursionHelper

+    public static partial class RecursionHelper

     {

-        #region 全排列，返回数据的所有组合

-        public static void Permutations<T>(List<T> dataList, ref List<List<T>> perms) 

-        {                                                                             

-            List<List<T>> outPerms = new List<List<T>>();                            //  A B C D 

-			List<T> temp = new List<T>(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;

-                },

-				(DivisionDescriptor div) => // solve 最小子任务处理   

-				{

-					temp.Add(dataList[div.left]);

-					List<T> newCompose = new List<T>(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<T>(List<T> data)

-        {

-            foreach (var perm in _Permutations(data, 0, data.Count - 1))

-            {

-                yield return perm;

-            }

-        }

-

-        // 计算start~end范围内的全排列

-        private static IEnumerable _Permutations<T>(List<T> data, int start, int end, List<T> perm = null)

-        {

-			if (perm == null)

-                perm = new List<T>(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

-

-        #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 DNC(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 动态规划

-

-        private static void DP()

-        {

-

-        }

-        #endregion 

-

 

     }

 }
\ No newline at end of file