diff options
Diffstat (limited to 'Assets/Algorithms/Recursion/Recursion_DC.cs')
| -rw-r--r-- | Assets/Algorithms/Recursion/Recursion_DC.cs | 144 |
1 files changed, 144 insertions, 0 deletions
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<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)
+ 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<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
+ }
+}
\ No newline at end of file |