diff options
Diffstat (limited to 'Assets/Algorithms/Recursion')
| -rw-r--r-- | Assets/Algorithms/Recursion/DivisionDescriptor.cs | 14 | ||||
| -rw-r--r-- | Assets/Algorithms/Recursion/DivisionDescriptor.cs.meta | 11 | ||||
| -rw-r--r-- | Assets/Algorithms/Recursion/Recursion.cs | 87 |
3 files changed, 61 insertions, 51 deletions
diff --git a/Assets/Algorithms/Recursion/DivisionDescriptor.cs b/Assets/Algorithms/Recursion/DivisionDescriptor.cs new file mode 100644 index 0000000..3a66456 --- /dev/null +++ b/Assets/Algorithms/Recursion/DivisionDescriptor.cs @@ -0,0 +1,14 @@ +using System.Collections;
+using System.Collections.Generic;
+using UnityEngine;
+
+namespace AlgorithmCollection.Recursion
+{
+ public struct DivisionDescriptor
+ {
+ public int left;
+ public int right;
+ public object userdata;
+ }
+
+}
\ No newline at end of file diff --git a/Assets/Algorithms/Recursion/DivisionDescriptor.cs.meta b/Assets/Algorithms/Recursion/DivisionDescriptor.cs.meta new file mode 100644 index 0000000..44ea263 --- /dev/null +++ b/Assets/Algorithms/Recursion/DivisionDescriptor.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: c0b30adfe2a7d364fb55f795a6c7f657 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Recursion/Recursion.cs b/Assets/Algorithms/Recursion/Recursion.cs index 4f2c4d3..c704f8f 100644 --- a/Assets/Algorithms/Recursion/Recursion.cs +++ b/Assets/Algorithms/Recursion/Recursion.cs @@ -5,42 +5,33 @@ 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) => // 划分
+ 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)
+ DivideAndConquer( // + 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) => // adhoc 最小子任务处理 // + B(C)
+ { // + C(B)
+ temp.Add(dataList[div.left]); // + B (ACD)
+ List<T> newCompose = new List<T>(temp); // + C (ABD)
+ outPerms.Add(newCompose); // + D (ABC)
+ temp.RemoveAt(temp.Count - 1);
+ },
+ (DivisionDescriptor div, out bool bAdhoc) => // 划分
{
int left = div.left; // 包含第一个元素在内的范围
int right = div.right;
@@ -66,7 +57,7 @@ namespace AlgorithmCollection.Recursion return divisions;
},
null, // 合并
- (IList<T> dataList, DivisionDescriptor div) => //子任务后处理
+ (DivisionDescriptor div) => //子任务后处理
{
int pivot = (int)div.userdata; // 第一个元素的索引
int left = div.left;
@@ -116,47 +107,41 @@ namespace AlgorithmCollection.Recursion #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 delegate DivisionDescriptor Init();
+ public delegate void AdHoc(DivisionDescriptor division);
+ public delegate DivisionDescriptor[] Divide(DivisionDescriptor division, out bool bAdhoc);
+ public delegate void Merge(DivisionDescriptor[] divisions);
+ public delegate void Postprocess(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)
+ public static void DivideAndConquer(Init init, AdHoc adhoc, Divide divide, Merge merge = null, Postprocess postprocess = null)
{
- DivisionDescriptor div = init(dataList);
- _DivideAndConquer(dataList, div, adhoc, divide, merge, postprocess);
+ DivisionDescriptor div = init();
+ _DivideAndConquer(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)
+ private static void _DivideAndConquer(DivisionDescriptor div, AdHoc adhoc, Divide divide, Merge merge, Postprocess postprocess)
{
bool bAdhoc;
- DivisionDescriptor[] division = divide(dataList, div, out bAdhoc);
+ DivisionDescriptor[] division = divide(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]);
+ _DivideAndConquer(division[i], adhoc, divide, merge, postprocess);
+ postprocess?.Invoke(division[i]);
}
- merge?.Invoke(dataList, division);
+ merge?.Invoke(division);
}
else
{
for(int i = 0; i < division.Length; ++i)
{
- adhoc(dataList, division[i]);
+ adhoc(division[i]);
}
}
}
- // 分治算法框架，非递归
- public static void DivideAndConquer_NoneRecursion<T>(IList<T> dataList, int threshold, AdHoc<T> adhoc, Divide<T> divide, Merge<T> merge)
- {
-
- }
-
#endregion
}
|