实例介绍
【实例简介】
调用示例:
//数组列表 string[] array = { "01", "02", "03", "04", "05", "06", "07", "08", "09", "10" }; //在其中选择6个数字 int lowerIndex = 6; var combinations = new Facet.Combinatorics.Combinations<String>( array, lowerIndex, Facet.Combinatorics.GenerateOption.WithoutRepetition ); List<string> list = new List<string>(); foreach (IList<String> combis in combinations) { string[] arr = new string[combis.Count]; combis.CopyTo(arr,0); String combi = String.Join(" ",arr ); //Console.WriteLine(combi); list.Add(combi); } //将组合结果总数以及具体值 输出 MessageBox.Show(list.Count.ToString() "\r\n" string.Join(",\r\n",list.ToArray()));
【实例截图】
【核心代码】
using System; using System.Collections.Generic; using System.Text; namespace Facet.Combinatorics { /// <summary> /// Combinations defines a meta-collection, typically a list of lists, of all possible /// subsets of a particular size from the set of values. This list is enumerable and /// allows the scanning of all possible combinations using a simple foreach() loop. /// Within the returned set, there is no prescribed order. This follows the mathematical /// concept of choose. For example, put 10 dominoes in a hat and pick 5. The number of possible /// combinations is defined as "10 choose 5", which is calculated as (10!) / ((10 - 5)! * 5!). /// </summary> /// <remarks> /// The MetaCollectionType parameter of the constructor allows for the creation of /// two types of sets, those with and without repetition in the output set when /// presented with repetition in the input set. /// /// When given a input collect {A B C} and lower index of 2, the following sets are generated: /// MetaCollectionType.WithRepetition => /// {A A}, {A B}, {A C}, {B B}, {B C}, {C C} /// MetaCollectionType.WithoutRepetition => /// {A B}, {A C}, {B C} /// /// Input sets with multiple equal values will generate redundant combinations in proprotion /// to the likelyhood of outcome. For example, {A A B B} and a lower index of 3 will generate: /// {A A B} {A A B} {A B B} {A B B} /// </remarks> /// <typeparam name="T">The type of the values within the list.</typeparam> public class Combinations<T> : IMetaCollection<T> { #region Constructors /// <summary> /// No default constructor, must provided a list of values and size. /// </summary> protected Combinations() { ; } /// <summary> /// Create a combination set from the provided list of values. /// The upper index is calculated as values.Count, the lower index is specified. /// Collection type defaults to MetaCollectionType.WithoutRepetition /// </summary> /// <param name="values">List of values to select combinations from.</param> /// <param name="lowerIndex">The size of each combination set to return.</param> public Combinations(IList<T> values, int lowerIndex) { Initialize(values, lowerIndex, GenerateOption.WithoutRepetition); } /// <summary> /// Create a combination set from the provided list of values. /// The upper index is calculated as values.Count, the lower index is specified. /// </summary> /// <param name="values">List of values to select combinations from.</param> /// <param name="lowerIndex">The size of each combination set to return.</param> /// <param name="type">The type of Combinations set to generate.</param> public Combinations(IList<T> values, int lowerIndex, GenerateOption type) { Initialize(values, lowerIndex, type); } #endregion #region IEnumerable Interface /// <summary> /// Gets an enumerator for collecting the list of combinations. /// </summary> /// <returns>The enumerator.</returns> public IEnumerator<IList<T>> GetEnumerator() { return new Enumerator(this); } /// <summary> /// Gets an enumerator for collecting the list of combinations. /// </summary> /// <returns>The enumerator.returns> System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return new Enumerator(this); } #endregion #region Enumerator Inner Class /// <summary> /// The enumerator that enumerates each meta-collection of the enclosing Combinations class. /// </summary> public class Enumerator : IEnumerator<IList<T>> { #region Constructors /// <summary> /// Construct a enumerator with the parent object. /// </summary> /// <param name="source">The source combinations object.</param> public Enumerator(Combinations<T> source) { myParent = source; myPermutationsEnumerator = (Permutations<bool>.Enumerator)myParent.myPermutations.GetEnumerator(); } #endregion #region IEnumerator interface /// <summary> /// Resets the combinations enumerator to the first combination. /// </summary> public void Reset() { myPermutationsEnumerator.Reset(); } /// <summary> /// Advances to the next combination of items from the set. /// </summary> /// <returns>True if successfully moved to next combination, False if no more unique combinations exist.</returns> /// <remarks> /// The heavy lifting is done by the permutations object, the combination is generated /// by creating a new list of those items that have a true in the permutation parrellel array. /// </remarks> public bool MoveNext() { bool ret = myPermutationsEnumerator.MoveNext(); myCurrentList = null; return ret; } /// <summary> /// The current combination /// </summary> public IList<T> Current { get { ComputeCurrent(); return myCurrentList; } } /// <summary> /// The current combination /// </summary> object System.Collections.IEnumerator.Current { get { ComputeCurrent(); return myCurrentList; } } /// <summary> /// Cleans up non-managed resources, of which there are none used here. /// </summary> public void Dispose() { ; } #endregion #region Heavy Lifting Members /// <summary> /// The only complex function of this entire wrapper, ComputeCurrent() creates /// a list of original values from the bool permutation provided. /// The exception for accessing current (InvalidOperationException) is generated /// by the call to .Current on the underlying enumeration. /// </summary> /// <remarks> /// To compute the current list of values, the underlying permutation object /// which moves with this enumerator, is scanned differently based on the type. /// The items have only two values, true and false, which have different meanings: /// /// For type WithoutRepetition, the output is a straightforward subset of the input array. /// E.g. 6 choose 3 without repetition /// Input array: {A B C D E F} /// Permutations: {0 1 0 0 1 1} /// Generates set: {A C D } /// Note: size of permutation is equal to upper index. /// /// For type WithRepetition, the output is defined by runs of characters and when to /// move to the next element. /// E.g. 6 choose 5 with repetition /// Input array: {A B C D E F} /// Permutations: {0 1 0 0 1 1 0 0 1 1} /// Generates set: {A B B D D } /// Note: size of permutation is equal to upper index - 1 lower index. /// </remarks> private void ComputeCurrent() { if(myCurrentList == null) { myCurrentList = new List<T>(); int index = 0; IList<bool> currentPermutation = (IList<bool>)myPermutationsEnumerator.Current; for(int i = 0; i < currentPermutation.Count; i) { if(currentPermutation[i] == false) { myCurrentList.Add(myParent.myValues[index]); if(myParent.Type == GenerateOption.WithoutRepetition) { index; } } else { index; } } } } #endregion #region Data /// <summary> /// Parent object this is an enumerator for. /// </summary> private Combinations<T> myParent; /// <summary> /// The current list of values, this is lazy evaluated by the Current property. /// </summary> private List<T> myCurrentList; /// <summary> /// An enumertor of the parents list of lexicographic orderings. /// </summary> private Permutations<bool>.Enumerator myPermutationsEnumerator; #endregion } #endregion #region IMetaList Interface /// <summary> /// The number of unique combinations that are defined in this meta-collection. /// This value is mathematically defined as Choose(M, N) where M is the set size /// and N is the subset size. This is M! / (N! * (M-N)!). /// </summary> public long Count { get { return myPermutations.Count; } } /// <summary> /// The type of Combinations set that is generated. /// </summary> public GenerateOption Type { get { return myMetaCollectionType; } } /// <summary> /// The upper index of the meta-collection, equal to the number of items in the initial set. /// </summary> public int UpperIndex { get { return myValues.Count; } } /// <summary> /// The lower index of the meta-collection, equal to the number of items returned each iteration. /// </summary> public int LowerIndex { get { return myLowerIndex; } } #endregion #region Heavy Lifting Members /// <summary> /// Initialize the combinations by settings a copy of the values from the /// </summary> /// <param name="values">List of values to select combinations from.</param> /// <param name="lowerIndex">The size of each combination set to return.</param> /// <param name="type">The type of Combinations set to generate.</param> /// <remarks> /// Copies the array and parameters and then creates a map of booleans that will /// be used by a permutations object to refence the subset. This map is slightly /// different based on whether the type is with or without repetition. /// /// When the type is WithoutRepetition, then a map of upper index elements is /// created with lower index false's. /// E.g. 8 choose 3 generates: /// Map: {1 1 1 1 1 0 0 0} /// Note: For sorting reasons, false denotes inclusion in output. /// /// When the type is WithRepetition, then a map of upper index - 1 lower index /// elements is created with the falses indicating that the 'current' element should /// be included and the trues meaning to advance the 'current' element by one. /// E.g. 8 choose 3 generates: /// Map: {1 1 1 1 1 1 1 1 0 0 0} (7 trues, 3 falses). /// </remarks> private void Initialize(IList<T> values, int lowerIndex, GenerateOption type) { myMetaCollectionType = type; myLowerIndex = lowerIndex; myValues = new List<T>(); myValues.AddRange(values); List<bool> myMap = new List<bool>(); if(type == GenerateOption.WithoutRepetition) { for(int i = 0; i < myValues.Count; i) { if(i >= myValues.Count - myLowerIndex) { myMap.Add(false); } else { myMap.Add(true); } } } else { for(int i = 0; i < values.Count - 1; i) { myMap.Add(true); } for(int i = 0; i < myLowerIndex; i) { myMap.Add(false); } } myPermutations = new Permutations<bool>(myMap); } #endregion #region Data /// <summary> /// Copy of values object is intialized with, required for enumerator reset. /// </summary> private List<T> myValues; /// <summary> /// Permutations object that handles permutations on booleans for combination inclusion. /// </summary> private Permutations<bool> myPermutations; /// <summary> /// The type of the combination collection. /// </summary> private GenerateOption myMetaCollectionType; /// <summary> /// The lower index defined in the constructor. /// </summary> private int myLowerIndex; #endregion } }
好例子网口号:伸出你的我的手 — 分享!
小贴士
感谢您为本站写下的评论,您的评论对其它用户来说具有重要的参考价值,所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字,对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙,所以请不要反馈意义不大的重复字符,也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明,或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦,又没人会搭理,于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享,对搜索内容的合法性不具有预见性、识别性、控制性,仅供学习研究,请务必在下载后24小时内给予删除,不得用于其他任何用途,否则后果自负。基于互联网的特殊性,平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查;无论平台是否已进行审查,用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场,基于网友分享,根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定,若资源存在侵权或相关问题请联系本站客服人员,点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论