From 75f032d79023fcf40dc8a52ebb2b3dc190aad609 Mon Sep 17 00:00:00 2001 From: chai Date: Tue, 22 Jun 2021 22:54:20 +0800 Subject: *divide --- Assets/Algorithms/Recursion/DivisionDescriptor.cs | 14 ++++ .../Recursion/DivisionDescriptor.cs.meta | 11 +++ Assets/Algorithms/Recursion/Recursion.cs | 87 +++++++++------------- Assets/Algorithms/Searching/SearchingHelper.cs | 10 +-- Assets/Test/05_Recursion/Test_Recursion.cs | 25 +++---- 5 files changed, 78 insertions(+), 69 deletions(-) create mode 100644 Assets/Algorithms/Recursion/DivisionDescriptor.cs create mode 100644 Assets/Algorithms/Recursion/DivisionDescriptor.cs.meta 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(List data, ref List> perms) // A B C D - { // + A (BCD) - List> outPerms = new List>(); // + B (CD) - List temp = new List(data.Count); // + C(D) - DivideAndConquer(data, // +D - (IList 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 dataList, DivisionDescriptor div) => // adhoc 最小子任务处理 // + B (ACD) - { // + C (ABD) - temp.Add(dataList[div.left]); // + D (ABC) - List newCompose = new List(temp); - outPerms.Add(newCompose); - temp.RemoveAt(temp.Count - 1); - }, - (IList dataList, DivisionDescriptor div, out bool bAdhoc) => // 划分 + public static void Permutations(List dataList, ref List> perms) + { + List> outPerms = new List>(); // A B C D + List temp = new List(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 newCompose = new List(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 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(IList dataList); - public delegate void AdHoc(IList dataList, DivisionDescriptor division); - public delegate DivisionDescriptor[] Divide(IList dataList, DivisionDescriptor division, out bool bAdhoc); - public delegate void Merge(IList dataList, DivisionDescriptor[] divisions); - public delegate void Postprocess(IList 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(IList dataList, Init init, AdHoc adhoc, Divide divide, Merge merge = null, Postprocess 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(IList dataList, DivisionDescriptor div, AdHoc adhoc, Divide divide, Merge merge, Postprocess 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(IList dataList, int threshold, AdHoc adhoc, Divide divide, Merge merge) - { - - } - #endregion } diff --git a/Assets/Algorithms/Searching/SearchingHelper.cs b/Assets/Algorithms/Searching/SearchingHelper.cs index 1605b43..a36e653 100644 --- a/Assets/Algorithms/Searching/SearchingHelper.cs +++ b/Assets/Algorithms/Searching/SearchingHelper.cs @@ -31,25 +31,25 @@ namespace AlgorithmCollection.Searching return -1; // 没找到 } - public static int BinarySearch(List dataList, T value) where T : IComparable, IEquatable + public static int BinarySearch(List data, T value) where T : IComparable, IEquatable { int index = -1; - RecursionHelper.DivideAndConquer(dataList, - (IList data) => + RecursionHelper.DivideAndConquer( + () => { DivisionDescriptor div = new DivisionDescriptor(); div.left = 0; div.right = data.Count - 1; return div; }, - (IList data, DivisionDescriptor div) => + (DivisionDescriptor div) => { if (data[div.left].CompareTo(value) == 0) { index = div.left; } }, - (IList data, DivisionDescriptor div, out bool bAdhoc) => + (DivisionDescriptor div, out bool bAdhoc) => { int left = div.left; int right = div.right; diff --git a/Assets/Test/05_Recursion/Test_Recursion.cs b/Assets/Test/05_Recursion/Test_Recursion.cs index 7529270..aef587c 100644 --- a/Assets/Test/05_Recursion/Test_Recursion.cs +++ b/Assets/Test/05_Recursion/Test_Recursion.cs @@ -21,21 +21,20 @@ public class Test_Recursion : MonoBehaviour void TestPermutations() { // 全排列 - //Debug.Log("全排列"); - //List data = new List { 'a', 'b', 'c' }; - //int count = 0; - //foreach (List p in RecursionHelper.Permutations(data)) - //{ - // count++; - // string content = ""; - // p.ForEach((char c) => content += c + " "); - // Debug.Log(content); - //} - //Debug.Assert(count == Algorithms.Factorial(data.Count)); - Debug.Log("全排列"); - List data = new List { 'a', 'b', 'c' , 'd'}; + List data = new List { 'a', 'b', 'c' }; int count = 0; + foreach (List p in RecursionHelper.Permutations(data)) + { + count++; + string content = ""; + p.ForEach((char c) => content += c + " "); + Debug.Log(content); + } + Debug.Assert(count == Algorithms.Factorial(data.Count)); + + Debug.Log("全排列"); + count = 0; List> perms = new List>(); RecursionHelper.Permutations(data, ref perms); foreach (List p in perms) -- cgit v1.1-26-g67d0