首页 > 代码库 > 算法(全排列算法封装)
算法(全排列算法封装)
本算法是教材中的全排列方法之一,本人仅做封装,在此感谢发现算法和传播算法的大牛们.
/// <summary> /// 全排列算法,算法原理:Perm(n)=[n]*Pern(n-1).N的全排列等于将N个数取一个放在第N个位置后,剩下的N-1个数做全排列。 /// 这个算法的一个用途是进行行列式的展开和计算,这也是这次封装这个算法的目的。 /// </summary> public class Permulation { /// <summary> /// 排列结果 /// </summary> private List<List<int>> _PermArray { get; set; } /// <summary> /// 去重用. /// </summary> private Dictionary<string, List<int>> _NoRepeatArray { get; set; } /// <summary> /// 要排列的整数数组 /// </summary> private int[] _Numbers { get; set; } /// <summary> /// 元素个数 /// </summary> private int _N { get; set; } /// <summary> /// 是否去重. /// </summary> private bool _RemoveDup { get; set; } /// <summary> /// 全排列计数 /// </summary> public int TotalCount { get; set; } /// <summary> /// 排列结果 /// </summary> public List<List<int>> PermulationArray { get { return _PermArray; } } /// <summary> /// 任意给定数字数组进行全排列 /// </summary> /// <param name="Numbers">数组</param> /// <param name="RemoveDup">是否去重</param> public Permulation(int[] Numbers, bool RemoveDup = false) { _NoRepeatArray = new Dictionary<string, List<int>>(); _PermArray = new List<List<int>>(); TotalCount = 0; _Numbers = Numbers; _N = Numbers.Count(); _RemoveDup = RemoveDup; } /// <summary> /// 自然数1-N全排列 /// </summary> /// <param name="N"></param> public Permulation(int N) { _PermArray = new List<List<int>>(); TotalCount = 0; _Numbers = new int[N]; for (int i = 1; i <= N; i++) { _Numbers[i - 1] = i; } _N = N; } /// <summary> /// 交换位置. /// </summary> /// <param name="Nums"></param> /// <param name="i"></param> /// <param name="j"></param> private void Swap(int[] Nums, int i, int j) { int theTemp = Nums[i - 1]; Nums[i - 1] = Nums[j - 1]; Nums[j - 1] = theTemp; } /// <summary> /// 执行全排列 /// </summary> public void DoCalculation() { DoArray(1); } /// <summary> /// 递归算法进行全排列. /// </summary> /// <param name="NextIndex"></param> private void DoArray(int NextIndex) { if (NextIndex > _N) { var theNums = new List<int>(); //利用字典本身的字符串哈希算法判重。 var theSeqStr = ""; for (int i = 0; i < _N; i++) { //注意这里需要分割,防止1 23和12 3之类造成的重复. theSeqStr += "," + _Numbers[i]; theNums.Add(_Numbers[i]); } if (_RemoveDup) { if (!_NoRepeatArray.ContainsKey(theSeqStr)) { _NoRepeatArray.Add(theSeqStr, theNums); _PermArray.Add(theNums); TotalCount++; } } else { _PermArray.Add(theNums); TotalCount++; } } else { //与后面的所有位置进行交换,但注意,每次交换完,应复原。 for (int i = NextIndex; i <= _N; i++) { Swap(_Numbers, NextIndex, i); DoArray(NextIndex + 1); //复原 Swap(_Numbers, NextIndex, i); } } } }
注:本算法只经过简单测试,没经过大批量测试。
算法(全排列算法封装)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。