diff options
Diffstat (limited to 'Assets/Algorithms/Recursion')
| -rw-r--r-- | Assets/Algorithms/Recursion/Recursion.cs | 129 |
1 files changed, 67 insertions, 62 deletions
diff --git a/Assets/Algorithms/Recursion/Recursion.cs b/Assets/Algorithms/Recursion/Recursion.cs index c704f8f..7bfb171 100644 --- a/Assets/Algorithms/Recursion/Recursion.cs +++ b/Assets/Algorithms/Recursion/Recursion.cs @@ -13,58 +13,55 @@ namespace AlgorithmCollection.Recursion #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)
- 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;
- 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;
+ List<List<T>> outPerms = new List<List<T>>(); // A B C D
+ List<T> temp = new List<T>(dataList.Count); // + A (BCD)
+ DNC( // + 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;
},
- null, // 合并
- (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);
- }
+ (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;
}
@@ -105,30 +102,30 @@ namespace AlgorithmCollection.Recursion }
#endregion
- #region 分治算法
+ #region 分治
public delegate DivisionDescriptor Init();
- public delegate void AdHoc(DivisionDescriptor division);
- public delegate DivisionDescriptor[] Divide(DivisionDescriptor division, out bool bAdhoc);
+ 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 DivideAndConquer(Init init, AdHoc adhoc, Divide divide, Merge merge = null, Postprocess postprocess = null)
+ public static void DNC(Init init, Divide divide, Solve solve, Postprocess postprocess = null, Merge merge = null)
{
DivisionDescriptor div = init();
- _DivideAndConquer(div, adhoc, divide, merge, postprocess);
+ _DivideAndConquer(div, solve, divide, merge, postprocess);
}
- private static void _DivideAndConquer(DivisionDescriptor div, AdHoc adhoc, Divide divide, Merge merge, Postprocess postprocess)
+ private static void _DivideAndConquer(DivisionDescriptor div, Solve solve, Divide divide, Merge merge, Postprocess postprocess)
{
- bool bAdhoc;
- DivisionDescriptor[] division = divide(div, out bAdhoc);
- if (!bAdhoc)
+ DivisionDescriptor[] division;
+ bool bUnit = divide(div, out division);
+ if (!bUnit)
{
for(int i = 0; i < division.Length; ++i)
{
- _DivideAndConquer(division[i], adhoc, divide, merge, postprocess);
+ _DivideAndConquer(division[i], solve, divide, merge, postprocess);
postprocess?.Invoke(division[i]);
}
merge?.Invoke(division);
@@ -137,12 +134,20 @@ namespace AlgorithmCollection.Recursion {
for(int i = 0; i < division.Length; ++i)
{
- adhoc(division[i]);
+ solve(division[i]);
}
}
}
+ #endregion
+
+ #region 动态规划
+ private static void DP()
+ {
+
+ }
#endregion
+
}
}
\ No newline at end of file |