diff options
Diffstat (limited to 'Assets/Algorithms/Recursion')
| -rw-r--r-- | Assets/Algorithms/Recursion/Recursion.cs | 163 | ||||
| -rw-r--r-- | Assets/Algorithms/Recursion/Recursion.cs.meta | 11 |
2 files changed, 174 insertions, 0 deletions
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 diff --git a/Assets/Algorithms/Recursion/Recursion.cs.meta b/Assets/Algorithms/Recursion/Recursion.cs.meta new file mode 100644 index 0000000..07aa1e2 --- /dev/null +++ b/Assets/Algorithms/Recursion/Recursion.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: d879b71db7b8d344fafd47ce8522aae3 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: |