summaryrefslogtreecommitdiff
path: root/Assets/Algorithms
diff options
context:
space:
mode:
Diffstat (limited to 'Assets/Algorithms')
-rw-r--r--Assets/Algorithms/Recursion/Recursion_DC.cs144
-rw-r--r--Assets/Algorithms/Recursion/Recursion_DC.cs.meta11
-rw-r--r--Assets/Algorithms/Recursion/Recursion_DP.cs106
-rw-r--r--Assets/Algorithms/Recursion/Recursion_DP.cs.meta11
4 files changed, 272 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
diff --git a/Assets/Algorithms/Recursion/Recursion_DC.cs.meta b/Assets/Algorithms/Recursion/Recursion_DC.cs.meta
new file mode 100644
index 0000000..46827b2
--- /dev/null
+++ b/Assets/Algorithms/Recursion/Recursion_DC.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 7f1f1be65b676ad46a43bd7515673e34
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Assets/Algorithms/Recursion/Recursion_DP.cs b/Assets/Algorithms/Recursion/Recursion_DP.cs
new file mode 100644
index 0000000..a0205ba
--- /dev/null
+++ b/Assets/Algorithms/Recursion/Recursion_DP.cs
@@ -0,0 +1,106 @@
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using AlgorithmCollection;
+using UnityEngine;
+
+// 动态规划算法
+namespace AlgorithmCollection.Recursion
+{
+
+ public static partial class RecursionHelper
+ {
+ //#region 动态规划框架
+ //private static void DP()
+ //{
+
+ //}
+ //#endregion
+
+ //最长公共子串
+ // longest common subpart
+ public static void FindLCSP<T>(T[] A, T[] B, ref List<T> result) where T : IEquatable<T>, IComparable
+ {
+ int end = 0;
+ int maxLen = 0;
+ int[,] dp = new int[A.Length, B.Length]; // 记录以A[i],B[j]结尾的子串的最长公共子串长度
+ for(int i = 0; i < A.Length; ++i)
+ { // 1, A[i]==B[j] && (i==0 || j==0)
+ for (int j = 0; j < B.Length; ++j) //dp[i,j] = dp[i-1,j-1]+1, A[i]==B[j] && i!=0 && j!=0
+ { // 0, A[i]!=B[j]
+ if(A[i].Equals(B[j]))
+ {
+ if (i == 0 || j == 0) // a b c b c e d
+ dp[i, j] = 1; // a 1 0 0 0 0 0 0
+ else // c 0 0 1 0 1 0 0
+ dp[i, j] = dp[i - 1, j - 1] + 1; // b 0 1 0 2 0 0 0
+ if (maxLen < dp[i, j]) // c 0 0 2 0 3 0 0
+ { // b 0 1 0 3 0 0 0
+ maxLen = dp[i, j]; // c 0 0 2 0 4 0 0
+ end = i; // e 0 0 0 0 0 5 0
+ } // f 0 0 0 0 0 0 0
+ }
+ }
+ }
+ if(maxLen > 0)
+ {
+ for (int i = 0; i < maxLen; ++i)
+ {
+ result.Add(A[end - maxLen + 1 + i]);
+ }
+ }
+ }
+
+ //最长公共子序列
+ // longest common subsequence
+ public static void FindLCSS<T>(T[] A, T[] B, ref List<T> result) where T : IEquatable<T>, IComparable
+ {
+ int[,] dp = new int[A.Length, B.Length]; // 记录[0-i]和[0-j]两个子串的最长公共子序列长度
+ int max = 0;
+ for (int i = 0; i < A.Length; ++i) // 1, A[i]==B[j] && (i==0 || j==0)
+ { //dp[i,j] = dp[i-1,j-1]+1, A[i]==B[j] && i!=0 && j!=0
+ for(int j = 0; j < B.Length; ++j) // 0, A[i]!=B[j] && (i==0 || j==0)
+ { // max(dp[i,j-1],dp[i-1,j]), A[i]!=B[j] && i!=0 && j!=0
+ if (A[i].Equals(B[j]))
+ { // a b c b c e d
+ if (i == 0 || j == 0) // a 1 1 1 1 1 1 1
+ dp[i, j] = 1; // c 1 1 2 2 2 2 2
+ else // b 1 2 2 3 3 3 3
+ dp[i, j] = dp[i - 1, j - 1] + 1; // c 1 2 3 3 4 4 4
+ if(max < dp[i, j]) // b 1 2 3 4 4 4 4
+ { // c 1 2 3 4 5 5 5
+ max = dp[i, j]; // e 1 2 3 4 5 6 6
+ result.Add(A[i]); // f 1 2 3 4 5 6 6
+ }
+ }
+ else
+ {
+ if (i == 0 || j == 0)
+ dp[i, j] = 0;
+ else
+ dp[i, j] = Algorithms.Max(dp[i - 1, j], dp[i, j - 1]);
+ }
+ }
+ }
+ Debug.Log(max);
+ }
+
+ // 计算最大子段和
+ public static int CalMaxSum(int[] nums)
+ {
+ int n = nums.Length;
+ int max = int.MinValue;
+ int sum = int.MinValue; //dp
+ for(int i = 0; i < n; ++i)
+ {
+ if (sum > 0)
+ sum += nums[i];
+ else
+ sum = nums[i];
+ max = Algorithms.Max(max, sum);
+ }
+ return max;
+ }
+
+ }
+} \ No newline at end of file
diff --git a/Assets/Algorithms/Recursion/Recursion_DP.cs.meta b/Assets/Algorithms/Recursion/Recursion_DP.cs.meta
new file mode 100644
index 0000000..fcaed18
--- /dev/null
+++ b/Assets/Algorithms/Recursion/Recursion_DP.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: e5aefe863ec10ec41a87358acf61f595
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
generated by cgit v1.1-26-g67d0 at 2025-05-18 19:50:17 +0000