diff options
| author | chai <chaifix@163.com> | 2021-06-21 15:53:42 +0800 |
|---|---|---|
| committer | chai <chaifix@163.com> | 2021-06-21 15:53:42 +0800 |
| commit | cc475a8b16b0e9323623c6532e114dceeb64353a (patch) | |
| tree | 0d57c6afd973ed03a66e614038d9c9ef1acb790b /Assets/Algorithms/Recursion.cs | |
| parent | 2283e4eda5ed0ef8760bef495b6ca60297b36404 (diff) | |
+recursions
Diffstat (limited to 'Assets/Algorithms/Recursion.cs')
| -rw-r--r-- | Assets/Algorithms/Recursion.cs | 63 |
1 files changed, 63 insertions, 0 deletions
diff --git a/Assets/Algorithms/Recursion.cs b/Assets/Algorithms/Recursion.cs new file mode 100644 index 0000000..30ebd8a --- /dev/null +++ b/Assets/Algorithms/Recursion.cs @@ -0,0 +1,63 @@ +using System;
+using System.Collections;
+using System.Collections.Generic;
+using AlgorithmCollection;
+
+// 递归与分治算法
+
+namespace AlgorithmCollection.Recursion
+{
+
+ public static class RecursionHelper
+ {
+
+ #region 全排列，返回数据的所有组合
+ public static void Permutations<T>(List<T> data, ref List<List<T>> perms)
+ {
+ if (perms == null)
+ perms = new List<List<T>>();
+ foreach(List<T> perm in perms)
+ {
+ List<T> p = new List<T>(perm);
+ perms.Add(p);
+ }
+ }
+
+ // 生成器形式，每次返回一个组合
+ 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 |