C#的排列组合类
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 |
//----------------------------------------------------------------------------- // // 算法：排列组合类 // // 版权所有(C) Snowdust // 个人博客 http://blog.csdn.net/snowdust & http://snowdust.cnblogs.com // MSN & Email snowdust77@sina.com // // 此源代码可免费用于各类软件（含商业软件） // 允许对此代码的进一步修改与开发 // 但必须完整保留此版权信息 // // 调用方法如下： // // 1.GetPermutation(T[], startIndex, endIndex) // 对startIndex到endIndex进行排列，其余元素不变 // // 2.GetPermutation(T[]) // 返回数组所有元素的全排列 // // 3.GetPermutation(T[], n) // 返回数组中n个元素的排列 // // 4.GetCombination(T[], n) // 返回数组中n个元素的组合 // // 版本历史： // V0.1 2010-01-20 摘要：首次创建 // //----------------------------------------------------------------------------- using System; using System.Collections.Generic; namespace Algorithms { public class PermutationAndCombination<T> { /// <summary> /// 交换两个变量 /// </summary> /// <param name="a">变量1</param> /// <param name="b">变量2</param> public static void Swap(ref T a, ref T b) { T temp = a; a = b; b = temp; } /// <summary> /// 递归算法求数组的组合(私有成员) /// </summary> /// <param name="list">返回的范型</param> /// <param name="t">所求数组</param> /// <param name="n">辅助变量</param> /// <param name="m">辅助变量</param> /// <param name="b">辅助数组</param> /// <param name="M">辅助变量M</param> private static void GetCombination(ref List<T[]> list, T[] t, int n, int m, int[] b, int M) { for (int i = n; i >= m; i--) { b[m - 1] = i - 1; if (m > 1) { GetCombination(ref list, t, i - 1, m - 1, b, M); } else { if (list == null) { list = new List<T[]>(); } T[] temp = new T[M]; for (int j = 0; j < b.Length; j++) { temp[j] = t[b[j]]; } list.Add(temp); } } } /// <summary> /// 递归算法求排列(私有成员) /// </summary> /// <param name="list">返回的列表</param> /// <param name="t">所求数组</param> /// <param name="startIndex">起始标号</param> /// <param name="endIndex">结束标号</param> private static void GetPermutation(ref List<T[]> list, T[] t, int startIndex, int endIndex) { if (startIndex == endIndex) { if (list == null) { list = new List<T[]>(); } T[] temp = new T[t.Length]; t.CopyTo(temp, 0); list.Add(temp); } else { for (int i = startIndex; i <= endIndex; i++) { Swap(ref t[startIndex], ref t[i]); GetPermutation(ref list, t, startIndex + 1, endIndex); Swap(ref t[startIndex], ref t[i]); } } } /// <summary> /// 求从起始标号到结束标号的排列，其余元素不变 /// </summary> /// <param name="t">所求数组</param> /// <param name="startIndex">起始标号</param> /// <param name="endIndex">结束标号</param> /// <returns>从起始标号到结束标号排列的范型</returns> public static List<T[]> GetPermutation(T[] t, int startIndex, int endIndex) { if (startIndex < 0 || endIndex > t.Length - 1) { return null; } List<T[]> list = new List<T[]>(); GetPermutation(ref list, t, startIndex, endIndex); return list; } /// <summary> /// 返回数组所有元素的全排列 /// </summary> /// <param name="t">所求数组</param> /// <returns>全排列的范型</returns> public static List<T[]> GetPermutation(T[] t) { return GetPermutation(t, 0, t.Length - 1); } /// <summary> /// 求数组中n个元素的排列 /// </summary> /// <param name="t">所求数组</param> /// <param name="n">元素个数</param> /// <returns>数组中n个元素的排列</returns> public static List<T[]> GetPermutation(T[] t, int n) { if (n > t.Length) { return null; } List<T[]> list = new List<T[]>(); List<T[]> c = GetCombination(t, n); for (int i = 0; i < c.Count; i++) { List<T[]> l = new List<T[]>(); GetPermutation(ref l, c[i], 0, n - 1); list.AddRange(l); } return list; } /// <summary> /// 求数组中n个元素的组合 /// </summary> /// <param name="t">所求数组</param> /// <param name="n">元素个数</param> /// <returns>数组中n个元素的组合的范型</returns> public static List<T[]> GetCombination(T[] t, int n) { if (t.Length < n) { return null; } int[] temp = new int[n]; List<T[]> list = new List<T[]>(); GetCombination(ref list, t, t.Length, n, temp, n); return list; } } } |
调用：
|
1 2 3 4 5 6 7 8 9 |
int[] arr = new int[6]; for (int i = 0; i < arr.Length; i++) { arr[i] = i + 1; } //求排列 List<int[]> lst_Permutation = Algorithms.PermutationAndCombination<int>.GetPermutation(arr, 3); //求组合 List<int[]> lst_Combination = Algorithms.PermutationAndCombination<int>.GetCombination(arr, 3); |
