From 8938c3447d88e31f77f20553ed185fc8e64c9ac8 Mon Sep 17 00:00:00 2001
From: chai <chaifix@163.com>
Date: Tue, 22 Jun 2021 14:58:53 +0800
Subject: +misc

---
 Assets/Algorithms/Recursion/Recursion.cs | 163 +++++++++++++++++++++++++++++++
 1 file changed, 163 insertions(+)
 create mode 100644 Assets/Algorithms/Recursion/Recursion.cs

(limited to 'Assets/Algorithms/Recursion/Recursion.cs')

diff --git a/Assets/Algorithms/Recursion/Recursion.cs b/Assets/Algorithms/Recursion/Recursion.cs
new file mode 100644
index 0000000..4f2c4d3
--- /dev/null
+++ b/Assets/Algorithms/Recursion/Recursion.cs
@@ -0,0 +1,163 @@
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using AlgorithmCollection;
+using UnityEngine;
+
+// 递归与分治算法
+
+namespace AlgorithmCollection.Recursion
+{
+
+    public struct DivisionDescriptor
+    {
+        public int left;
+        public int right;
+        public object userdata;
+    }
+
+    public static class RecursionHelper
+    {
+        #region 全排列，返回数据的所有组合
+
+        public static void Permutations<T>(List<T> data, ref List<List<T>> perms)          //  A B C D 
+        {                                                                                  //  + A (BCD)
+            List<List<T>> outPerms = new List<List<T>>();                                  //  	+ B (CD)
+            List<T> temp = new List<T>(data.Count);                                        //  		+ C(D)
+            DivideAndConquer(data,                                                         //  			+D
+                (IList<T> dataList) => // init                                             //  		+ D(C)
+                {                                                                          //  			+C
+                    DivisionDescriptor div = new DivisionDescriptor();                     //  	+ C (BD)
+                    div.userdata = -1;                                                     //  		+ B(D)
+                    div.left = 0;                                                          //  		+ D(B)
+                    div.right = dataList.Count - 1;                                        //  	+ D (BC)
+                    return div;                                                            //  		+ B(C)
+                },                                                                         //  		+ C(B)
+                (IList<T> dataList, DivisionDescriptor div) => // adhoc 最小子任务处理      //  + B (ACD)
+                {                                                                          //  + C (ABD)
+                    temp.Add(dataList[div.left]);                                          //  + D (ABC)
+                    List<T> newCompose = new List<T>(temp);                                
+                    outPerms.Add(newCompose);                                              
+                    temp.RemoveAt(temp.Count - 1);                                         
+                },                                                                         
+                (IList<T> dataList, 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;
+                },
+                null, // 合并
+                (IList<T> dataList, 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<T>(IList<T> dataList);
+        public delegate void AdHoc<T>(IList<T> dataList, DivisionDescriptor division);
+        public delegate DivisionDescriptor[] Divide<T>(IList<T> dataList, DivisionDescriptor division, out bool bAdhoc);
+        public delegate void Merge<T>(IList<T> dataList, DivisionDescriptor[] divisions);
+        public delegate void Postprocess<T>(IList<T> dataList, DivisionDescriptor div);
+
+        // 分治算法框架
+        public static void DivideAndConquer<T>(IList<T> dataList, Init<T> init, AdHoc<T> adhoc, Divide<T> divide, Merge<T> merge = null, Postprocess<T> postprocess = null)
+        {
+            DivisionDescriptor div = init(dataList);
+            _DivideAndConquer(dataList, div, adhoc, divide, merge, postprocess);
+        }
+
+        private static void _DivideAndConquer<T>(IList<T> dataList, DivisionDescriptor div, AdHoc<T> adhoc, Divide<T> divide, Merge<T> merge, Postprocess<T> postprocess)
+        {
+            bool bAdhoc;
+            DivisionDescriptor[] division = divide(dataList, div, out bAdhoc);
+            if (!bAdhoc)
+            {
+                for(int i = 0; i < division.Length; ++i)
+                {
+                    _DivideAndConquer(dataList, division[i], adhoc, divide, merge, postprocess);
+                    postprocess?.Invoke(dataList, division[i]);
+                }
+                merge?.Invoke(dataList, division);
+            }
+            else
+            {
+                for(int i = 0; i < division.Length; ++i)
+                {
+                    adhoc(dataList, division[i]);
+                }
+            }
+        }
+
+        // 分治算法框架，非递归
+        public static void DivideAndConquer_NoneRecursion<T>(IList<T> dataList, int threshold, AdHoc<T> adhoc, Divide<T> divide, Merge<T> merge)
+        {
+
+        }
+
+        #endregion 
+
+    }
+}
\ No newline at end of file
-- 
cgit v1.1-26-g67d0