11,935,345 members (64,041 online)

600.8K views
187 bookmarked
Posted

Permutations, Combinations, and Variations using C# Generics

, 23 May 2008 CPOL
Discusses the six major types of combinatorial collections, with examples and formulas for counting. Expands with a C# Generics-based set of classes for enumerating each meta-collection.
 combinatoricssample.zip CombinatoricsSample TextSumProblemSample bin Debug Release Combinatorics Facet.ico obj Debug Refactor TempPE Release TempPE Properties Settings.settings TextSumProblemSample.csproj.user textsumproblemsample.zip TextSumProblemSample.exe ```// Copyright 2008 Adrian Akison // Distributed under license terms of CPOL http://www.codeproject.com/info/cpol10.aspx using System; using System.Collections.Generic; using System.Text; namespace Facet.Combinatorics { /// /// Variations defines a meta-collection, typically a list of lists, of all possible /// ordered subsets of a particular size from the set of values. /// This list is enumerable and allows the scanning of all possible Variations using a simple /// foreach() loop even though the variations are not all in memory. /// /// /// The MetaCollectionType parameter of the constructor allows for the creation of /// normal Variations and Variations with Repetition. /// /// When given an input collect {A B C} and lower index of 2, the following sets are generated: /// MetaCollectionType.WithoutRepetition generates 6 sets: => /// {A B}, {A B}, {B A}, {B C}, {C A}, {C B} /// MetaCollectionType.WithRepetition generates 9 sets: /// {A A}, {A B}, {A B}, {B A}, {B B }, {B C}, {C A}, {C B}, {C C} /// /// The equality of multiple inputs is not considered when generating variations. /// /// The type of the values within the list. public class Variations : IMetaCollection { #region Constructors /// /// No default constructor, must provided a list of values and size. /// protected Variations() { ; } /// /// Create a variation set from the indicated list of values. /// The upper index is calculated as values.Count, the lower index is specified. /// Collection type defaults to MetaCollectionType.WithoutRepetition /// /// List of values to select Variations from. /// The size of each variation set to return. public Variations(IList values, int lowerIndex) { Initialize(values, lowerIndex, GenerateOption.WithoutRepetition); } /// /// Create a variation set from the indicated list of values. /// The upper index is calculated as values.Count, the lower index is specified. /// /// List of values to select variations from. /// The size of each vatiation set to return. /// Type indicates whether to use repetition in set generation. public Variations(IList values, int lowerIndex, GenerateOption type) { Initialize(values, lowerIndex, type); } #endregion #region IEnumerable Interface /// /// Gets an enumerator for the collection of Variations. /// /// The enumerator. public IEnumerator> GetEnumerator() { if(Type == GenerateOption.WithRepetition) { return new EnumeratorWithRepetition(this); } else { return new EnumeratorWithoutRepetition(this); } } /// /// Gets an enumerator for the collection of Variations. /// /// The enumerator. System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { if(Type == GenerateOption.WithRepetition) { return new EnumeratorWithRepetition(this); } else { return new EnumeratorWithoutRepetition(this); } } #endregion #region Enumerator Inner Class /// /// An enumerator for Variations when the type is set to WithRepetition. /// public class EnumeratorWithRepetition : IEnumerator> { #region Constructors /// /// Construct a enumerator with the parent object. /// /// The source Variations object. public EnumeratorWithRepetition(Variations source) { myParent = source; Reset(); } #endregion #region IEnumerator interface /// /// Resets the Variations enumerator to the first variation. /// public void Reset() { myCurrentList = null; myListIndexes = null; } /// /// Advances to the next variation. /// /// True if successfully moved to next variation, False if no more variations exist. /// /// Increments the internal myListIndexes collection by incrementing the last index /// and overflow/carrying into others just like grade-school arithemtic. If the /// finaly carry flag is set, then we would wrap around and are therefore done. /// public bool MoveNext() { int carry = 1; if(myListIndexes == null) { myListIndexes = new List(); for(int i = 0; i < myParent.LowerIndex; ++i) { myListIndexes.Add(0); } carry = 0; } else { for(int i = myListIndexes.Count - 1; i >= 0 && carry > 0; --i) { myListIndexes[i] += carry; carry = 0; if(myListIndexes[i] >= myParent.UpperIndex) { myListIndexes[i] = 0; carry = 1; } } } myCurrentList = null; return carry != 1; } /// /// The current variation /// public IList Current { get { ComputeCurrent(); return myCurrentList; } } /// /// The current variation. /// object System.Collections.IEnumerator.Current { get { ComputeCurrent(); return myCurrentList; } } /// /// Cleans up non-managed resources, of which there are none used here. /// public void Dispose() { ; } #endregion #region Heavy Lifting Members /// /// Computes the current list based on the internal list index. /// private void ComputeCurrent() { if(myCurrentList == null) { myCurrentList = new List(); foreach(int index in myListIndexes) { myCurrentList.Add(myParent.myValues[index]); } } } #endregion #region Data /// /// Parent object this is an enumerator for. /// private Variations myParent; /// /// The current list of values, this is lazy evaluated by the Current property. /// private List myCurrentList; /// /// An enumertor of the parents list of lexicographic orderings. /// private List myListIndexes; #endregion } /// /// An enumerator for Variations when the type is set to WithoutRepetition. /// public class EnumeratorWithoutRepetition : IEnumerator> { #region Constructors /// /// Construct a enumerator with the parent object. /// /// The source Variations object. public EnumeratorWithoutRepetition(Variations source) { myParent = source; myPermutationsEnumerator = (Permutations.Enumerator)myParent.myPermutations.GetEnumerator(); } #endregion #region IEnumerator interface /// /// Resets the Variations enumerator to the first variation. /// public void Reset() { myPermutationsEnumerator.Reset(); } /// /// Advances to the next variation. /// /// True if successfully moved to next variation, False if no more variations exist. public bool MoveNext() { bool ret = myPermutationsEnumerator.MoveNext(); myCurrentList = null; return ret; } /// /// The current variation. /// public IList Current { get { ComputeCurrent(); return myCurrentList; } } /// /// The current variation. /// object System.Collections.IEnumerator.Current { get { ComputeCurrent(); return myCurrentList; } } /// /// Cleans up non-managed resources, of which there are none used here. /// public void Dispose() { ; } #endregion #region Heavy Lifting Members /// /// Creates a list of original values from the int permutation provided. /// The exception for accessing current (InvalidOperationException) is generated /// by the call to .Current on the underlying enumeration. /// /// /// To compute the current list of values, the element to use is determined by /// a permutation position with a non-MaxValue value. It is placed at the position in the /// output that the index value indicates. /// /// E.g. Variations of 6 choose 3 without repetition /// Input array: {A B C D E F} /// Permutations: {- 1 - - 3 2} (- is Int32.MaxValue) /// Generates set: {B F E} /// private void ComputeCurrent() { if(myCurrentList == null) { myCurrentList = new List(); int index = 0; IList currentPermutation = (IList)myPermutationsEnumerator.Current; for(int i = 0; i < myParent.LowerIndex; ++i) { myCurrentList.Add(myParent.myValues[0]); } for(int i = 0; i < currentPermutation.Count; ++i) { int position = currentPermutation[i]; if(position != Int32.MaxValue) { myCurrentList[position] = myParent.myValues[index]; if(myParent.Type == GenerateOption.WithoutRepetition) { ++index; } } else { ++index; } } } } #endregion #region Data /// /// Parent object this is an enumerator for. /// private Variations myParent; /// /// The current list of values, this is lazy evaluated by the Current property. /// private List myCurrentList; /// /// An enumertor of the parents list of lexicographic orderings. /// private Permutations.Enumerator myPermutationsEnumerator; #endregion } #endregion #region IMetaList Interface /// /// The number of unique variations that are defined in this meta-collection. /// /// /// Variations with repetitions does not behave like other meta-collections and it's /// count is equal to N^P, where N is the upper index and P is the lower index. /// public long Count { get { if(Type == GenerateOption.WithoutRepetition) { return myPermutations.Count; } else { return (long)Math.Pow(UpperIndex, LowerIndex); } } } /// /// The type of Variations set that is generated. /// public GenerateOption Type { get { return myMetaCollectionType; } } /// /// The upper index of the meta-collection, equal to the number of items in the initial set. /// public int UpperIndex { get { return myValues.Count; } } /// /// The lower index of the meta-collection, equal to the number of items returned each iteration. /// public int LowerIndex { get { return myLowerIndex; } } #endregion #region Heavy Lifting Members /// /// Initialize the variations for constructors. /// /// List of values to select variations from. /// The size of each variation set to return. /// The type of variations set to generate. private void Initialize(IList values, int lowerIndex, GenerateOption type) { myMetaCollectionType = type; myLowerIndex = lowerIndex; myValues = new List(); myValues.AddRange(values); if(type == GenerateOption.WithoutRepetition) { List myMap = new List(); int index = 0; for(int i = 0; i < myValues.Count; ++i) { if(i >= myValues.Count - myLowerIndex) { myMap.Add(index++); } else { myMap.Add(Int32.MaxValue); } } myPermutations = new Permutations(myMap); } else { ; // myPermutations isn't used. } } #endregion #region Data /// /// Copy of values object is intialized with, required for enumerator reset. /// private List myValues; /// /// Permutations object that handles permutations on int for variation inclusion and ordering. /// private Permutations myPermutations; /// /// The type of the variation collection. /// private GenerateOption myMetaCollectionType; /// /// The lower index defined in the constructor. /// private int myLowerIndex; #endregion } } ```

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.