|
|
// 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>
/// 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.
/// </summary>
/// <remarks>
/// 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.
/// </remarks>
/// <typeparam name="T">The type of the values within the list.</typeparam>
public class Variations<T> : IMetaCollection<T> {
#region Constructors
/// <summary>
/// No default constructor, must provided a list of values and size.
/// </summary>
protected Variations() {
;
}
/// <summary>
/// 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
/// </summary>
/// <param name="values">List of values to select Variations from.</param>
/// <param name="lowerIndex">The size of each variation set to return.</param>
public Variations(IList<T> values, int lowerIndex) {
Initialize(values, lowerIndex, GenerateOption.WithoutRepetition);
}
/// <summary>
/// Create a variation set from the indicated 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 variations from.</param>
/// <param name="lowerIndex">The size of each vatiation set to return.</param>
/// <param name="type">Type indicates whether to use repetition in set generation.</param>
public Variations(IList<T> values, int lowerIndex, GenerateOption type) {
Initialize(values, lowerIndex, type);
}
#endregion
#region IEnumerable Interface
/// <summary>
/// Gets an enumerator for the collection of Variations.
/// </summary>
/// <returns>The enumerator.</returns>
public IEnumerator<IList<T>> GetEnumerator() {
if(Type == GenerateOption.WithRepetition) {
return new EnumeratorWithRepetition(this);
}
else {
return new EnumeratorWithoutRepetition(this);
}
}
/// <summary>
/// Gets an enumerator for the collection of Variations.
/// </summary>
/// <returns>The enumerator.</returns>
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
/// <summary>
/// An enumerator for Variations when the type is set to WithRepetition.
/// </summary>
public class EnumeratorWithRepetition : IEnumerator<IList<T>> {
#region Constructors
/// <summary>
/// Construct a enumerator with the parent object.
/// </summary>
/// <param name="source">The source Variations object.</param>
public EnumeratorWithRepetition(Variations<T> source) {
myParent = source;
Reset();
}
#endregion
#region IEnumerator interface
/// <summary>
/// Resets the Variations enumerator to the first variation.
/// </summary>
public void Reset() {
myCurrentList = null;
myListIndexes = null;
}
/// <summary>
/// Advances to the next variation.
/// </summary>
/// <returns>True if successfully moved to next variation, False if no more variations exist.</returns>
/// <remarks>
/// 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.
/// </remarks>
public bool MoveNext() {
int carry = 1;
if(myListIndexes == null) {
myListIndexes = new List<int>();
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;
}
/// <summary>
/// The current variation
/// </summary>
public IList<T> Current {
get {
ComputeCurrent();
return myCurrentList;
}
}
/// <summary>
/// The current variation.
/// </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>
/// Computes the current list based on the internal list index.
/// </summary>
private void ComputeCurrent() {
if(myCurrentList == null) {
myCurrentList = new List<T>();
foreach(int index in myListIndexes) {
myCurrentList.Add(myParent.myValues[index]);
}
}
}
#endregion
#region Data
/// <summary>
/// Parent object this is an enumerator for.
/// </summary>
private Variations<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 List<int> myListIndexes;
#endregion
}
/// <summary>
/// An enumerator for Variations when the type is set to WithoutRepetition.
/// </summary>
public class EnumeratorWithoutRepetition : IEnumerator<IList<T>> {
#region Constructors
/// <summary>
/// Construct a enumerator with the parent object.
/// </summary>
/// <param name="source">The source Variations object.</param>
public EnumeratorWithoutRepetition(Variations<T> source) {
myParent = source;
myPermutationsEnumerator = (Permutations<int>.Enumerator)myParent.myPermutations.GetEnumerator();
}
#endregion
#region IEnumerator interface
/// <summary>
/// Resets the Variations enumerator to the first variation.
/// </summary>
public void Reset() {
myPermutationsEnumerator.Reset();
}
/// <summary>
/// Advances to the next variation.
/// </summary>
/// <returns>True if successfully moved to next variation, False if no more variations exist.</returns>
public bool MoveNext() {
bool ret = myPermutationsEnumerator.MoveNext();
myCurrentList = null;
return ret;
}
/// <summary>
/// The current variation.
/// </summary>
public IList<T> Current {
get {
ComputeCurrent();
return myCurrentList;
}
}
/// <summary>
/// The current variation.
/// </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>
/// 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.
/// </summary>
/// <remarks>
/// 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}
/// </remarks>
private void ComputeCurrent() {
if(myCurrentList == null) {
myCurrentList = new List<T>();
int index = 0;
IList<int> currentPermutation = (IList<int>)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
/// <summary>
/// Parent object this is an enumerator for.
/// </summary>
private Variations<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<int>.Enumerator myPermutationsEnumerator;
#endregion
}
#endregion
#region IMetaList Interface
/// <summary>
/// The number of unique variations that are defined in this meta-collection.
/// </summary>
/// <remarks>
/// 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.
/// </remarks>
public long Count {
get {
if(Type == GenerateOption.WithoutRepetition) {
return myPermutations.Count;
}
else {
return (long)Math.Pow(UpperIndex, LowerIndex);
}
}
}
/// <summary>
/// The type of Variations 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 variations for constructors.
/// </summary>
/// <param name="values">List of values to select variations from.</param>
/// <param name="lowerIndex">The size of each variation set to return.</param>
/// <param name="type">The type of variations set to generate.</param>
private void Initialize(IList<T> values, int lowerIndex, GenerateOption type) {
myMetaCollectionType = type;
myLowerIndex = lowerIndex;
myValues = new List<T>();
myValues.AddRange(values);
if(type == GenerateOption.WithoutRepetition) {
List<int> myMap = new List<int>();
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<int>(myMap);
}
else {
; // myPermutations isn't used.
}
}
#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 int for variation inclusion and ordering.
/// </summary>
private Permutations<int> myPermutations;
/// <summary>
/// The type of the variation 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