12,447,786 members (63,671 online)

641.6K views
195 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 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; using System.Collections.Generic; namespace Facet.Combinatorics { /// /// Permutations defines a meta-collection, typically a list of lists, of all /// possible orderings of a set of values. This list is enumerable and allows /// the scanning of all possible permutations using a simple foreach() loop. /// 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 A B}, the following sets are generated: /// MetaCollectionType.WithRepetition => /// {A A B}, {A B A}, {A A B}, {A B A}, {B A A}, {B A A} /// MetaCollectionType.WithoutRepetition => /// {A A B}, {A B A}, {B A A} /// /// When generating non-repetition sets, ordering is based on the lexicographic /// ordering of the lists based on the provided Comparer. /// If no comparer is provided, then T must be IComparable on T. /// /// When generating repetition sets, no comparisions are performed and therefore /// no comparer is required and T does not need to be IComparable. /// /// The type of the values within the list. public class Permutations : IMetaCollection { #region Constructors /// /// No default constructor, must at least provided a list of values. /// protected Permutations() { ; } /// /// Create a permutation set from the provided list of values. /// The values (T) must implement IComparable. /// If T does not implement IComparable use a constructor with an explict IComparer. /// The repetition type defaults to MetaCollectionType.WithholdRepetitionSets /// /// List of values to permute. public Permutations(IList values) { Initialize(values, GenerateOption.WithoutRepetition, null); } /// /// Create a permutation set from the provided list of values. /// If type is MetaCollectionType.WithholdRepetitionSets, then values (T) must implement IComparable. /// If T does not implement IComparable use a constructor with an explict IComparer. /// /// List of values to permute. /// The type of permutation set to calculate. public Permutations(IList values, GenerateOption type) { Initialize(values, type, null); } /// /// Create a permutation set from the provided list of values. /// The values will be compared using the supplied IComparer. /// The repetition type defaults to MetaCollectionType.WithholdRepetitionSets /// /// List of values to permute. /// Comparer used for defining the lexigraphic order. public Permutations(IList values, IComparer comparer) { Initialize(values, GenerateOption.WithoutRepetition, comparer); } #endregion #region IEnumerable Interface /// /// Gets an enumerator for collecting the list of permutations. /// /// The enumerator. public virtual IEnumerator GetEnumerator() { return new Enumerator(this); } /// /// Gets an enumerator for collecting the list of permutations. /// /// The enumerator. IEnumerator> IEnumerable>.GetEnumerator() { return new Enumerator(this); } #endregion #region Enumerator Inner-Class /// /// The enumerator that enumerates each meta-collection of the enclosing Permutations class. /// public class Enumerator : IEnumerator> { #region Constructors /// /// Construct a enumerator with the parent object. /// /// The source Permutations object. public Enumerator(Permutations source) { myParent = source; myLexicographicalOrders = new int[source.myLexicographicOrders.Length]; source.myLexicographicOrders.CopyTo(myLexicographicalOrders, 0); Reset(); } #endregion #region IEnumerator Interface /// /// Resets the permutations enumerator to the first permutation. /// This will be the first lexicographically order permutation. /// public void Reset() { myPosition = Position.BeforeFirst; } /// /// Advances to the next permutation. /// /// True if successfully moved to next permutation, False if no more permutations exist. /// /// Continuation was tried (i.e. yield return) by was not nearly as efficient. /// Performance is further increased by using value types and removing generics, that is, the LexicographicOrder parellel array. /// This is a issue with the .NET CLR not optimizing as well as it could in this infrequently used scenario. /// public bool MoveNext() { if(myPosition == Position.BeforeFirst) { myValues = new List(myParent.myValues.Count); myValues.AddRange(myParent.myValues); Array.Sort(myLexicographicalOrders); myPosition = Position.InSet; } else if(myPosition == Position.InSet) { if(myValues.Count < 2) { myPosition = Position.AfterLast; } else if(NextPermutation() == false) { myPosition = Position.AfterLast; } } return myPosition != Position.AfterLast; } /// /// The current permutation. /// public object Current { get { if(myPosition == Position.InSet) { return new List(myValues); } else { throw new InvalidOperationException(); } } } /// /// The current permutation. /// IList IEnumerator>.Current { get { if(myPosition == Position.InSet) { return new List(myValues); } else { throw new InvalidOperationException(); } } } /// /// Cleans up non-managed resources, of which there are none used here. /// public virtual void Dispose() { ; } #endregion #region Heavy Lifting Methods /// /// Calculates the next lexicographical permutation of the set. /// This is a permutation with repetition where values that compare as equal will not /// swap positions to create a new permutation. /// http://www.cut-the-knot.org/do_you_know/AllPerm.shtml /// E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1997 /// /// True if a new permutation has been returned, false if not. /// /// This uses the integers of the lexicographical order of the values so that any /// comparison of values are only performed during initialization. /// private bool NextPermutation() { int i = myLexicographicalOrders.Length - 1; while(myLexicographicalOrders[i - 1] >= myLexicographicalOrders[i]) { --i; if(i == 0) { return false; } } int j = myLexicographicalOrders.Length; while(myLexicographicalOrders[j - 1] <= myLexicographicalOrders[i - 1]) { --j; } Swap(i - 1, j - 1); ++i; j = myLexicographicalOrders.Length; while(i < j) { Swap(i - 1, j - 1); ++i; --j; } return true; } /// /// Helper function for swapping two elements within the internal collection. /// This swaps both the lexicographical order and the values, maintaining the parallel array. /// private void Swap(int i, int j) { myTemp = myValues[i]; myValues[i] = myValues[j]; myValues[j] = myTemp; myKviTemp = myLexicographicalOrders[i]; myLexicographicalOrders[i] = myLexicographicalOrders[j]; myLexicographicalOrders[j] = myKviTemp; } #endregion #region Data and Internal Members /// /// Single instance of swap variable for T, small performance improvement over declaring in Swap function scope. /// private T myTemp; /// /// Single instance of swap variable for int, small performance improvement over declaring in Swap function scope. /// private int myKviTemp; /// /// Flag indicating the position of the enumerator. /// private Position myPosition = Position.BeforeFirst; /// /// Parrellel array of integers that represent the location of items in the myValues array. /// This is generated at Initialization and is used as a performance speed up rather that /// comparing T each time, much faster to let the CLR optimize around integers. /// private int[] myLexicographicalOrders; /// /// The list of values that are current to the enumerator. /// private List myValues; /// /// The set of permuations that this enumerator enumerates. /// private Permutations myParent; /// /// Internal position type for tracking enumertor position. /// private enum Position { BeforeFirst, InSet, AfterLast } #endregion } #endregion #region IMetaList Interface /// /// The count of all permutations that will be returned. /// If type is MetaCollectionType.WithholdGeneratedSets, then this does not double count permutations with multiple identical values. /// I.e. count of permutations of "AAB" will be 3 instead of 6. /// If type is MetaCollectionType.WithRepetition, then this is all combinations and is therefore N!, where N is the number of values. /// public long Count { get { return myCount; } } /// /// The type of Permutations 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. /// For Permutation, this is always equal to the UpperIndex. /// public int LowerIndex { get { return myValues.Count; } } #endregion #region Heavy Lifting Members /// /// Common intializer used by the multiple flavors of constructors. /// /// /// Copies information provided and then creates a parellel int array of lexicographic /// orders that will be used for the actual permutation algorithm. /// The input array is first sorted as required for WithoutRepetition and always just for consistency. /// This array is constructed one of two way depending on the type of the collection. /// /// When type is MetaCollectionType.WithRepetition, then all N! permutations are returned /// and the lexicographic orders are simply generated as 1, 2, ... N. /// E.g. /// Input array: {A A B C D E E} /// Lexicograhpic Orders: {1 2 3 4 5 6 7} /// /// When type is MetaCollectionType.WithoutRepetition, then fewer are generated, with each /// identical element in the input array not repeated. The lexicographic sort algorithm /// handles this natively as long as the repetition is repeated. /// E.g. /// Input array: {A A B C D E E} /// Lexicograhpic Orders: {1 1 2 3 4 5 5} /// private void Initialize(IList values, GenerateOption type, IComparer comparer) { myMetaCollectionType = type; myValues = new List(values.Count); myValues.AddRange(values); myLexicographicOrders = new int[values.Count]; if(type == GenerateOption.WithRepetition) { for(int i = 0; i < myLexicographicOrders.Length; ++i) { myLexicographicOrders[i] = i; } } else { if(comparer == null) { comparer = new SelfComparer(); } myValues.Sort(comparer); int j = 1; if(myLexicographicOrders.Length > 0) { myLexicographicOrders[0] = j; } for(int i = 1; i < myLexicographicOrders.Length; ++i) { if(comparer.Compare(myValues[i - 1], myValues[i]) != 0) { ++j; } myLexicographicOrders[i] = j; } } myCount = GetCount(); } /// /// Calculates the total number of permutations that will be returned. /// As this can grow very large, extra effort is taken to avoid overflowing the accumulator. /// While the algorithm looks complex, it really is just collecting numerator and denominator terms /// and cancelling out all of the denominator terms before taking the product of the numerator terms. /// /// The number of permutations. private long GetCount() { int runCount = 1; List divisors = new List(); List numerators = new List(); for(int i = 1; i < myLexicographicOrders.Length; ++i) { numerators.AddRange(SmallPrimeUtility.Factor(i + 1)); if(myLexicographicOrders[i] == myLexicographicOrders[i - 1]) { ++runCount; } else { for(int f = 2; f <= runCount; ++f) { divisors.AddRange(SmallPrimeUtility.Factor(f)); } runCount = 1; } } for(int f = 2; f <= runCount; ++f) { divisors.AddRange(SmallPrimeUtility.Factor(f)); } return SmallPrimeUtility.EvaluatePrimeFactors(SmallPrimeUtility.DividePrimeFactors(numerators, divisors)); } #endregion #region Data and Internal Members /// /// A list of T that represents the order of elements as originally provided, used for Reset. /// private List myValues; /// /// Parrellel array of integers that represent the location of items in the myValues array. /// This is generated at Initialization and is used as a performance speed up rather that /// comparing T each time, much faster to let the CLR optimize around integers. /// private int[] myLexicographicOrders; /// /// Inner class that wraps an IComparer around a type T when it is IComparable /// private class SelfComparer : IComparer { public int Compare(U x, U y) { return ((IComparable)x).CompareTo(y); } } /// /// The count of all permutations. Calculated at Initialization and returned by Count property. /// private long myCount; /// /// The type of Permutations that this was intialized from. /// private GenerateOption myMetaCollectionType; #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
Web02 | 2.8.160811.3 | Last Updated 23 May 2008