排列组合的概念
排列：从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列(arrangement)。
组合：从m个不同的元素中，任取n（n≤m）个元素为一组，叫作从m个不同元素中取出n个元素的一个组合。
排列组合实现代码
上一个项目做的一个水路的路径规划时，用到了排列的数据结构。求任意n个点里m个点的不同顺序的组合个数。
这样求最优路径。下面贴一段不知道哪里找的排列组合的算法。
|
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
|
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; } } |
求组合：求5个数里任意3个数的组合
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
static void main(string[] args){int[] intarr = new int[] { 1, 2, 3, 4, 5 }; //整型数组list<int[]> listcombination = permutationandcombination<int>.getcombination(intarr, 3); //求全部的3-3组合foreach(int[] arr in listcombination){foreach(int item in arr){console.write(item + " ");}console.writeline("");}console.readkey();} |
求排列：5个数取3个的任意排列
|
1
2
3
4
5
6
7
8
9
10
|
int[] intarr = new int[] { 1, 2, 3, 4, 5 }; //整型数组list<int[]> listcombination = permutationandcombination<int>.getpermutation(intarr, 3); //求全部的5取3排列foreach(int[] arr in listcombination){foreach(int item in arr){console.write(item + " ");}console.writeline("");} |
以上就是本文的全部内容，希望对大家有所帮助！
原文链接：http://www.cnblogs.com/kissdodog/p/5419981.html
