详解C#的排列组合
作者:逆心 时间:2021-06-05 15:40:11
排列组合的概念
排列:从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排成一列,叫做从n个元素中取出m个元素的一个排列(Arrangement)。
组合:从m个不同的元素中,任取n(n≤m)个元素为一组,叫作从m个不同元素中取出n个元素的一个组合。
排列组合实现代码
上一个项目做的一个水路的路径规划时,用到了排列的数据结构。求任意N个点里M个点的不同顺序的组合个数。
这样求最优路径。下面贴一段不知道哪里找的排列组合的算法。
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个数的组合
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个的任意排列
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
标签:C#排列组合
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
spring boot多数据源动态切换代码实例
2022-03-11 00:37:09
![](https://img.aspxhome.com/file/2023/7/71867_0s.png)
Java实现学生选课管理系统
2023-04-12 20:00:16
![](https://img.aspxhome.com/file/2023/8/88068_0s.jpg)
Java SpringBoot在RequestBody中高效的使用枚举参数原理案例详解
2022-03-28 01:47:18
![](https://img.aspxhome.com/file/2023/4/71684_0s.jpg)
浅谈java项目与javaweb项目导入jar包的区别
2023-11-11 11:06:19
C# 设计模式系列教程-策略模式
2022-04-30 16:09:03
![](https://img.aspxhome.com/file/2023/1/106511_0s.png)
详解Spring Boot2 Webflux的全局异常处理
2023-11-09 02:12:25
C#实现身份证号码验证的方法
2022-11-08 09:15:34
设置Android系统永不锁屏永不休眠的方法
2021-06-28 12:01:21
C#枚举类型与位域枚举Enum
2023-03-02 06:52:27
Java switch使用原理及实例解析
2023-10-11 20:44:20
IDEA使用Gradle构建SpringBoot项目工程的详细教程
2022-08-31 16:28:26
![](https://img.aspxhome.com/file/2023/1/84221_0s.png)
Struts2拦截器 关于解决登录的问题
2023-07-02 14:06:09
![](https://img.aspxhome.com/file/2023/1/78241_0s.png)
Android开发中ImageLoder进行图片加载和缓存
2023-08-18 10:14:30
Android实现淘宝客户端倒计时界面
2023-09-18 21:25:09
![](https://img.aspxhome.com/file/2023/9/93309_0s.gif)
对Java中传值调用的理解分析
2023-05-03 15:22:14
使用spring容器在初始化Bean时前和后的操作
2021-07-01 05:49:24
SpringBoot利用拦截器实现避免重复请求
2022-02-07 00:21:53
![](https://img.aspxhome.com/file/2023/1/68021_0s.png)
Spring Boot中操作使用Redis实现详解
2023-11-24 02:39:29
![](https://img.aspxhome.com/file/2023/9/85399_0s.png)
深入浅析Java 抽象类和接口
2022-12-17 19:19:27
![](https://img.aspxhome.com/file/2023/3/67133_0s.png)
C#实现为一张大尺寸图片创建缩略图的方法
2021-08-03 21:07:15