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 +++++++++------------- 3 files changed, 61 insertions(+), 51 deletions(-) create mode 100644 Assets/Algorithms/Recursion/DivisionDescriptor.cs create mode 100644 Assets/Algorithms/Recursion/DivisionDescriptor.cs.meta (limited to 'Assets/Algorithms/Recursion') 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 } -- cgit v1.1-26-g67d0