12,950,618 members (57,963 online)

#### Stats

679.4K views
201 bookmarked
Posted 13 May 2008

# 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 TextSumProblemSample bin Debug Release Combinatorics Facet.ico obj Debug Refactor TempPE Release TempPE Properties TextSumProblemSample.csproj.user 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 { /// /// 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!). /// /// /// 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} /// /// The type of the values within the list. public class Combinations : IMetaCollection { #region Constructors /// /// No default constructor, must provided a list of values and size. /// protected Combinations() { ; } /// /// 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 /// /// List of values to select combinations from. /// The size of each combination set to return. public Combinations(IList values, int lowerIndex) { Initialize(values, lowerIndex, GenerateOption.WithoutRepetition); } /// /// Create a combination set from the provided list of values. /// The upper index is calculated as values.Count, the lower index is specified. /// /// List of values to select combinations from. /// The size of each combination set to return. /// The type of Combinations set to generate. public Combinations(IList values, int lowerIndex, GenerateOption type) { Initialize(values, lowerIndex, type); } #endregion #region IEnumerable Interface /// /// Gets an enumerator for collecting the list of combinations. /// /// The enumerator. public IEnumerator> GetEnumerator() { return new Enumerator(this); } /// /// Gets an enumerator for collecting the list of combinations. /// /// The enumerator.returns> System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return new Enumerator(this); } #endregion #region Enumerator Inner Class /// /// The enumerator that enumerates each meta-collection of the enclosing Combinations class. /// public class Enumerator : IEnumerator> { #region Constructors /// /// Construct a enumerator with the parent object. /// /// The source combinations object. public Enumerator(Combinations source) { myParent = source; myPermutationsEnumerator = (Permutations.Enumerator)myParent.myPermutations.GetEnumerator(); } #endregion #region IEnumerator interface /// /// Resets the combinations enumerator to the first combination. /// public void Reset() { myPermutationsEnumerator.Reset(); } /// /// Advances to the next combination of items from the set. /// /// True if successfully moved to next combination, False if no more unique combinations exist. /// /// 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. /// public bool MoveNext() { bool ret = myPermutationsEnumerator.MoveNext(); myCurrentList = null; return ret; } /// /// The current combination /// public IList Current { get { ComputeCurrent(); return myCurrentList; } } /// /// The current combination /// 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 /// /// 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. /// /// /// 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. /// private void ComputeCurrent() { if(myCurrentList == null) { myCurrentList = new List(); int index = 0; IList currentPermutation = (IList)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 /// /// Parent object this is an enumerator for. /// private Combinations 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 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)!). /// public long Count { get { return myPermutations.Count; } } /// /// The type of Combinations 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 combinations by settings a copy of the values from the /// /// List of values to select combinations from. /// The size of each combination set to return. /// The type of Combinations set to generate. /// /// 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). /// private void Initialize(IList values, int lowerIndex, GenerateOption type) { myMetaCollectionType = type; myLowerIndex = lowerIndex; myValues = new List(); myValues.AddRange(values); List myMap = new List(); 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(myMap); } #endregion #region Data /// /// Copy of values object is intialized with, required for enumerator reset. /// private List myValues; /// /// Permutations object that handles permutations on booleans for combination inclusion. /// private Permutations myPermutations; /// /// The type of the combination 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.

## Share

 Team Leader Zuuse Pty Ltd Australia
I have been a professional software developer for twenty years, starting with C++ and migrated to C#. While I have transitioned into full time management, writing code is still my passion. As I don't write code for work very often, I have had the opportunity to apply my programming skills as a hobby where I have recently authored two Windows 8 store apps. First, an Asteroids tribute game, 'Roid Rage and most recently Shared Whiteboard (which does what it says).

I make a habit of contributing production code to every project I run. Most notably, I have recently run teams to build The Navigator for The Advertiser newspaper and Street Lights Out for SA Power Networks.

## You may also be interested in...

 Pro Pro