|
|
// 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 {
/// <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
}
}
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
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.
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.
Submit an article or tip