排列组合的概念
排列：从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
如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）
发表评论
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。