Skip to content

Instantly share code, notes, and snippets.

@alfaproject

alfaproject/Combinations.cs Secret

Last active August 29, 2015 14:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save alfaproject/cb68e6fa1c21e1f93bf7 to your computer and use it in GitHub Desktop.
Save alfaproject/cb68e6fa1c21e1f93bf7 to your computer and use it in GitHub Desktop.
Download ZIP
Best fleet calculator
Raw
Combinations.cs
// 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 aLfPoP.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> : IEnumerable<IList<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
/// <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
}
/// <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;
}
}
#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
}
}
Raw
GenerateOption.cs
namespace aLfPoP.Combinatorics
{
/// <summary>
/// Indicates whether a Permutation, Combination or Variation meta-collections
/// generate repetition sets.
/// </summary>
public enum GenerateOption
{
/// <summary>
/// Do not generate additional sets, typical implementation.
/// </summary>
WithoutRepetition,
/// <summary>
/// Generate additional sets even if repetition is required.
/// </summary>
WithRepetition
}
}
Raw
Permutations.cs
using System;
using System.Collections;
using System.Collections.Generic;
namespace aLfPoP.Combinatorics
{
/// <summary>
/// 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.
/// </summary>
/// <remarks>
/// 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.
/// </remarks>
/// <typeparam name="T">The type of the values within the list.</typeparam>
public class Permutations<T> : IEnumerable<IList<T>>
{
/// <summary>
/// A list of T that represents the order of elements as originally provided, used for Reset.
/// </summary>
private readonly List<T> _values;
/// <summary>
/// Parallel array of integers that represent the location of items in the _values 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.
/// </summary>
private readonly int[] _lexicographicOrders;
/// <summary>
/// Create a permutation set from the provided list of values.
/// The values will be compared using the supplied IComparer.
/// </summary>
/// <remarks>
/// Copies information provided and then creates a parallel 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}
/// </remarks>
/// <param name="values">List of values to permute.</param>
/// <param name="type">The type of permutation set to calculate.</param>
/// <param name="comparer">Comparer used for defining the lexigraphic order.</param>
public Permutations(IEnumerable<T> values, GenerateOption type, IComparer<T> comparer)
{
Type = type;
_values = new List<T>(values);
_lexicographicOrders = new int[_values.Count];
if (type == GenerateOption.WithRepetition)
{
for (var i = 0; i < _lexicographicOrders.Length; i++)
{
_lexicographicOrders[i] = i;
}
}
else
{
if (comparer == null)
{
comparer = Comparer<T>.Default;
}
_values.Sort(comparer);
var j = 1;
if (_lexicographicOrders.Length > 0)
{
_lexicographicOrders[0] = j;
}
for (var i = 1; i < _lexicographicOrders.Length; i++)
{
if (comparer.Compare(_values[i - 1], _values[i]) != 0)
{
j++;
}
_lexicographicOrders[i] = j;
}
}
}
/// <summary>
/// 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.
/// </summary>
/// <param name="values">List of values to permute.</param>
/// <param name="type">The type of permutation set to calculate.</param>
public Permutations(IEnumerable<T> values, GenerateOption type)
: this(values, type, null)
{
}
/// <summary>
/// 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
/// </summary>
/// <param name="values">List of values to permute.</param>
/// <param name="comparer">Comparer used for defining the lexigraphic order.</param>
public Permutations(IEnumerable<T> values, IComparer<T> comparer)
: this(values, GenerateOption.WithoutRepetition, comparer)
{
}
/// <summary>
/// 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
/// </summary>
/// <param name="values">List of values to permute.</param>
public Permutations(IEnumerable<T> values)
: this(values, GenerateOption.WithoutRepetition, null)
{
}
/// <summary>
/// The type of Permutations set that is generated.
/// </summary>
public GenerateOption Type
{
get;
private set;
}
/// <summary>
/// Gets an enumerator for collecting the list of permutations.
/// </summary>
/// <returns>The enumerator.</returns>
public virtual IEnumerator GetEnumerator()
{
return new Enumerator(this);
}
/// <summary>
/// Gets an enumerator for collecting the list of permutations.
/// </summary>
/// <returns>The enumerator.</returns>
IEnumerator<IList<T>> IEnumerable<IList<T>>.GetEnumerator()
{
return new Enumerator(this);
}
/// <summary>
/// The enumerator that enumerates each meta-collection of the enclosing Permutations class.
/// </summary>
public class Enumerator : IEnumerator<IList<T>>
{
/// <summary>
/// Single instance of swap variable for T, small performance improvement over declaring in Swap function scope.
/// </summary>
private T _temp;
/// <summary>
/// Single instance of swap variable for int, small performance improvement over declaring in Swap function scope.
/// </summary>
private int _kviTemp;
/// <summary>
/// Flag indicating the position of the enumerator.
/// </summary>
private Position _position = Position.BeforeFirst;
/// <summary>
/// Parallel array of integers that represent the location of items in the _values 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.
/// </summary>
private readonly int[] _lexicographicalOrders;
/// <summary>
/// The list of values that are current to the enumerator.
/// </summary>
private List<T> _values;
/// <summary>
/// The set of permuations that this enumerator enumerates.
/// </summary>
private readonly Permutations<T> _parent;
/// <summary>
/// Internal position type for tracking enumertor position.
/// </summary>
private enum Position
{
BeforeFirst,
InSet,
AfterLast
}
/// <summary>
/// Construct a enumerator with the parent object.
/// </summary>
/// <param name="source">The source Permutations object.</param>
public Enumerator(Permutations<T> source)
{
_parent = source;
_lexicographicalOrders = new int[source._lexicographicOrders.Length];
source._lexicographicOrders.CopyTo(_lexicographicalOrders, 0);
Reset();
}
/// <summary>
/// Resets the permutations enumerator to the first permutation.
/// This will be the first lexicographically order permutation.
/// </summary>
public void Reset()
{
_position = Position.BeforeFirst;
}
/// <summary>
/// Advances to the next permutation.
/// </summary>
/// <returns>True if successfully moved to next permutation, False if no more permutations exist.</returns>
/// <remarks>
/// 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 parallel array.
/// This is a issue with the .NET CLR not optimizing as well as it could in this infrequently used scenario.
/// </remarks>
public bool MoveNext()
{
switch (_position)
{
case Position.BeforeFirst:
_values = new List<T>(_parent._values);
Array.Sort(_lexicographicalOrders);
_position = Position.InSet;
break;
case Position.InSet:
if (_values.Count < 2)
{
_position = Position.AfterLast;
}
else if (NextPermutation() == false)
{
_position = Position.AfterLast;
}
break;
}
return _position != Position.AfterLast;
}
/// <summary>
/// The current permutation.
/// </summary>
public object Current
{
get
{
if (_position == Position.InSet)
{
return new List<T>(_values);
}
throw new InvalidOperationException();
}
}
/// <summary>
/// The current permutation.
/// </summary>
IList<T> IEnumerator<IList<T>>.Current
{
get
{
if (_position == Position.InSet)
{
return new List<T>(_values);
}
throw new InvalidOperationException();
}
}
/// <summary>
/// Cleans up non-managed resources, of which there are none used here.
/// </summary>
public virtual void Dispose()
{
}
/// <summary>
/// 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
/// </summary>
/// <returns>True if a new permutation has been returned, false if not.</returns>
/// <remarks>
/// This uses the integers of the lexicographical order of the values so that any
/// comparison of values are only performed during initialization.
/// </remarks>
private bool NextPermutation()
{
int i = _lexicographicalOrders.Length - 1;
while (_lexicographicalOrders[i - 1] >= _lexicographicalOrders[i])
{
--i;
if (i == 0)
{
return false;
}
}
int j = _lexicographicalOrders.Length;
while (_lexicographicalOrders[j - 1] <= _lexicographicalOrders[i - 1])
{
--j;
}
Swap(i - 1, j - 1);
++i;
j = _lexicographicalOrders.Length;
while (i < j)
{
Swap(i - 1, j - 1);
++i;
--j;
}
return true;
}
/// <summary>
/// Helper function for swapping two elements within the internal collection.
/// This swaps both the lexicographical order and the values, maintaining the parallel array.
/// </summary>
private void Swap(int i, int j)
{
_temp = _values[i];
_values[i] = _values[j];
_values[j] = _temp;
_kviTemp = _lexicographicalOrders[i];
_lexicographicalOrders[i] = _lexicographicalOrders[j];
_lexicographicalOrders[j] = _kviTemp;
}
}
}
}
Raw
PermutationsWithoutRepetition.cs
using System;
using System.Collections;
using System.Collections.Generic;
namespace aLfPoP.Combinatorics
{
/// <summary>
/// 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.
/// </summary>
/// <remarks>
/// 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.
/// </remarks>
/// <typeparam name="T">The type of the values within the list.</typeparam>
public class PermutationsWithoutRepetition<T> : IEnumerable<IList<T>>
{
/// <summary>
/// A list of T that represents the order of elements as originally provided, used for Reset.
/// </summary>
private readonly List<T> _values;
/// <summary>
/// Parallel array of integers that represent the location of items in the _values 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.
/// </summary>
private readonly int[] _lexicographicOrders;
/// <summary>
/// Create a permutation set from the provided list of values.
/// The values will be compared using the supplied IComparer.
/// </summary>
/// <remarks>
/// Copies information provided and then creates a parallel 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}
/// </remarks>
/// <param name="values">List of values to permute.</param>
/// <param name="type">The type of permutation set to calculate.</param>
/// <param name="comparer">Comparer used for defining the lexigraphic order.</param>
public PermutationsWithoutRepetition(IEnumerable<T> values)
{
_values = new List<T>(values);
_lexicographicOrders = new int[_values.Count];
_values.Sort();
var j = 1;
if (_lexicographicOrders.Length > 0)
{
_lexicographicOrders[0] = j;
}
for (var i = 1; i < _lexicographicOrders.Length; i++)
{
if (Comparer<T>.Default.Compare(_values[i - 1], _values[i]) != 0)
{
j++;
}
_lexicographicOrders[i] = j;
}
}
/// <summary>
/// Gets an enumerator for collecting the list of permutations.
/// </summary>
/// <returns>The enumerator.</returns>
public virtual IEnumerator GetEnumerator()
{
return new Enumerator(this);
}
/// <summary>
/// Gets an enumerator for collecting the list of permutations.
/// </summary>
/// <returns>The enumerator.</returns>
IEnumerator<IList<T>> IEnumerable<IList<T>>.GetEnumerator()
{
return new Enumerator(this);
}
/// <summary>
/// The enumerator that enumerates each meta-collection of the enclosing Permutations class.
/// </summary>
public class Enumerator : IEnumerator<IList<T>>
{
/// <summary>
/// Single instance of swap variable for T, small performance improvement over declaring in Swap function scope.
/// </summary>
private T _temp;
/// <summary>
/// Single instance of swap variable for int, small performance improvement over declaring in Swap function scope.
/// </summary>
private int _kviTemp;
/// <summary>
/// Flag indicating the position of the enumerator.
/// </summary>
private Position _position = Position.BeforeFirst;
/// <summary>
/// Parallel array of integers that represent the location of items in the _values 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.
/// </summary>
private readonly int[] _lexicographicalOrders;
/// <summary>
/// The list of values that are current to the enumerator.
/// </summary>
private List<T> _values;
/// <summary>
/// The set of permuations that this enumerator enumerates.
/// </summary>
private readonly PermutationsWithoutRepetition<T> _parent;
/// <summary>
/// Internal position type for tracking enumertor position.
/// </summary>
private enum Position
{
BeforeFirst,
InSet,
AfterLast
}
/// <summary>
/// Construct a enumerator with the parent object.
/// </summary>
/// <param name="source">The source Permutations object.</param>
public Enumerator(PermutationsWithoutRepetition<T> source)
{
_parent = source;
_lexicographicalOrders = new int[source._lexicographicOrders.Length];
source._lexicographicOrders.CopyTo(_lexicographicalOrders, 0);
Reset();
}
/// <summary>
/// Resets the permutations enumerator to the first permutation.
/// This will be the first lexicographically order permutation.
/// </summary>
public void Reset()
{
_position = Position.BeforeFirst;
}
/// <summary>
/// Advances to the next permutation.
/// </summary>
/// <returns>True if successfully moved to next permutation, False if no more permutations exist.</returns>
/// <remarks>
/// 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 parallel array.
/// This is a issue with the .NET CLR not optimizing as well as it could in this infrequently used scenario.
/// </remarks>
public bool MoveNext()
{
switch (_position)
{
case Position.BeforeFirst:
_values = new List<T>(_parent._values.Count);
_values.AddRange(_parent._values);
Array.Sort(_lexicographicalOrders);
_position = Position.InSet;
break;
case Position.InSet:
if (_values.Count < 2)
{
_position = Position.AfterLast;
}
else if (NextPermutation() == false)
{
_position = Position.AfterLast;
}
break;
}
return _position != Position.AfterLast;
}
/// <summary>
/// The current permutation.
/// </summary>
public object Current
{
get
{
if (_position == Position.InSet)
{
return new List<T>(_values);
}
throw new InvalidOperationException();
}
}
/// <summary>
/// The current permutation.
/// </summary>
IList<T> IEnumerator<IList<T>>.Current
{
get
{
if (_position == Position.InSet)
{
return new List<T>(_values);
}
throw new InvalidOperationException();
}
}
/// <summary>
/// Cleans up non-managed resources, of which there are none used here.
/// </summary>
public virtual void Dispose()
{
}
/// <summary>
/// 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
/// </summary>
/// <returns>True if a new permutation has been returned, false if not.</returns>
/// <remarks>
/// This uses the integers of the lexicographical order of the values so that any
/// comparison of values are only performed during initialization.
/// </remarks>
private bool NextPermutation()
{
int i = _lexicographicalOrders.Length - 1;
while (_lexicographicalOrders[i - 1] >= _lexicographicalOrders[i])
{
--i;
if (i == 0)
{
return false;
}
}
int j = _lexicographicalOrders.Length;
while (_lexicographicalOrders[j - 1] <= _lexicographicalOrders[i - 1])
{
--j;
}
Swap(i - 1, j - 1);
++i;
j = _lexicographicalOrders.Length;
while (i < j)
{
Swap(i - 1, j - 1);
++i;
--j;
}
return true;
}
/// <summary>
/// Helper function for swapping two elements within the internal collection.
/// This swaps both the lexicographical order and the values, maintaining the parallel array.
/// </summary>
private void Swap(int i, int j)
{
_temp = _values[i];
_values[i] = _values[j];
_values[j] = _temp;
_kviTemp = _lexicographicalOrders[i];
_lexicographicalOrders[i] = _lexicographicalOrders[j];
_lexicographicalOrders[j] = _kviTemp;
}
}
}
}
Raw
Program.cs
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading.Tasks;
using aLfPoP.Combinatorics;
namespace aLfPoP
{
static class Program
{
private static readonly object _syncLock = new object();
private static void Main(string[] args)
{
var rams = new[] {
new Unit(800, 0, 0, 0, 0, "Inspiring Figurehead"),
new Unit(0, 800, 0, 0, 0, "Spitfire Cannon"),
};
var decks = new[] {
new Unit(1350, 0, 0, 0, 0, "Eastern Relics"),
new Unit(0, 1750, 0, 0, 0, "Ov. Large Cannon x4"),
new Unit(0, 0, 1350, 0, 0, "Dragonskin Rigging"),
};
var hulls = new[] {
new Unit(1400, 500, 500, 600, 0, "Blazing Lantern Hull"),
new Unit(500, 1400, 500, 600, 0, "Golden Katana Hull"),
new Unit(500, 500, 1200, 400, 0, "Storm Rider Hull"),
};
var captains = new[] {
new Unit(1450, 770, 850, 800, 10, "Barnabas Wytche", Traits.Seafarer | Traits.ToughAsNails | Traits.FastLearner | Traits.MultiTalented),
new Unit(1420, 740, 740, 780, 10, "Sebastian Wytche", Traits.EagleEyed | Traits.MiseryGuts | Traits.Plucky | Traits.QuickFooted),
new Unit(650, 1510, 850, 800, 10, "Charlotte Fang", Traits.EagleEyed | Traits.Vapid | Traits.Loyal | Traits.MultiTalented),
new Unit(800, 800, 1500, 1050, 10, "Maladetta Hook", Traits.Loyal | Traits.MultiTalented | Traits.Workhorse | Traits.MultiTalented),
new Unit(805, 805, 1450, 865, 8, "Maladetta Kidd", Traits.Plucky | Traits.Eager | Traits.MultiTalented | Traits.MultiTalented),
}.OrderBy(c => c.Morale + c.Combat + c.Seafar).ToArray();
var roster = new[] {
// specials
new Unit(900, 900, 910, 0, 10, "Judge of Dice 1", Traits.Solidarity),
new Unit(900, 940, 910, 0, 10, "Judge of Dice 2", Traits.Solidarity | Traits.Plucky),
new Unit(1030, 1050, 1040, 0, 10, "Oxhead and Horseface 1", Traits.Plucky | Traits.Resurrects),
new Unit(1000, 1030, 1000, 0, 10, "Oxhead and Horseface 2", Traits.Resurrects),
// morale
new Unit(2440, 30, 0, 0, 10, "Travelling Band 1", Traits.Eager),
new Unit(2420, 50, 0, 0, 10, "Travelling Band 2", Traits.Plucky),
new Unit(2410, 20, 40, 20, 10, "Travelling Band 3", Traits.EagleEyed),
new Unit(2410, 0, 0, 0, 10, "Travelling Band 4"),
new Unit(2400, 0, 50, 10, 10, "Travelling Band 5"),
new Unit(2330, 10, 0, 10, 9, "Travelling Band 6"),
new Unit(2280, 0, 0, 0, 9, "Travelling Band 7"),
// combat
new Unit(-40, 2440, 0, 0, 10, "Ferocious Tiger-Rider 1", Traits.MiseryGuts),
new Unit(20, 2410, 0, 0, 10, "Ferocious Tiger-Rider 2"),
new Unit(10, 2400, -10, 0, 10, "Ferocious Tiger-Rider 3", Traits.ShortSighted),
new Unit(0, 2400, 0, 0, 10, "Ferocious Tiger-Rider 4"),
new Unit(0, 2400, 0, 0, 10, "Ferocious Tiger-Rider 5"),
new Unit(-40, 2400, 0, 30, 10, "Ferocious Tiger-Rider 6", Traits.MiseryGuts),
new Unit(30, 2700, 20, 0, 8, "Sea-fort Guard 1"),
// seafaring
new Unit(10, 50, 2400, 10, 10, "Harem of Fortune Tellers 1"),
new Unit(0, 0, 2400, 10, 10, "Harem of Fortune Tellers 2"),
new Unit(0, 40, 2400, 0, 10, "Harem of Fortune Tellers 3"),
new Unit(50, 0, 2400, 50, 10, "Harem of Fortune Tellers 4"),
new Unit(40, 20, 2430, 0, 10, "Harem of Fortune Tellers 5", Traits.Eager),
new Unit(60, 80, 2450, 100, 10, "Harem of Fortune Tellers 6", Traits.MultiTalented),
new Unit(0, 70, 2710, 0, 8, "Pearl Diver 1", Traits.Plucky),
}.OrderBy(c => c.Morale + c.Combat + c.Seafar);
var voyages = new[] {
new Voyage(115, 115, 1),
new Voyage(115, 1, 115),
new Voyage(1, 115, 115),
//new Voyage(115, 115, 115),
};
var crews = GetCombinationsWithoutRepetition(roster.ToList(), 5).OrderBy(c => c.Sum(m => m.Level)).ToList();
Console.WriteLine("Total crew combinations: " + crews.Count);
var stopwatch = new Stopwatch();
stopwatch.Start();
var possibleVoyages = PossibleVoyages(rams, decks, hulls, captains, crews, 50, new List<Ship>());
foreach (var possibleVoyage in possibleVoyages)
{
// we need to calculate rating of each ship somehow
Console.WriteLine(possibleVoyage.GetHashCode());
}
/*
// get ship combinations for every voyage
Parallel.ForEach(voyages, voyage =>
{
voyage.Ships = voyage.GetPossibleShips(93, rams, decks, hulls, captains, crews).OrderByDescending(s => s.Rate).ToList();
Console.WriteLine(voyage);
});
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);
stopwatch.Start();
for (var fleetSize = 1; fleetSize <= Math.Min(3, voyages.Length); fleetSize++)
{
Parallel.ForEach(new Combinations<Voyage>(voyages, fleetSize), voyagesCombo =>
{
Ship[] bestFleet = null;
switch (fleetSize)
{
case 3:
bestFleet = GetBestFleet3(voyagesCombo);
break;
case 2:
//bestFleet = GetBestFleet2(voyagesCombo);
break;
case 1:
//bestFleet = GetBestFleet1(voyagesCombo);
break;
}
if (bestFleet == null)
{
return;
}
lock (_syncLock)
{
Console.WriteLine("=================================================================");
for (var i = 0; i < fleetSize; i++)
{
var ship = bestFleet[i];
Console.WriteLine("\n******* {0} *******", voyagesCombo[i]);
Console.WriteLine("Ram\t{0}", ship.Ram);
Console.WriteLine("Deck1\t{0}", ship.Deck1);
Console.WriteLine("Deck2\t{0}", ship.Deck2);
Console.WriteLine("Hull\t{0}", ship.Hull);
Console.WriteLine("Captain\t{0}", ship.Captain);
foreach (var crewMember in ship.Crew)
{
Console.WriteLine("Crew\t{0}", crewMember);
}
Console.WriteLine("\t{0}\t{1}\t{2}\t{3}\t{4}%", ship.Morale, ship.Combat, ship.Seafar, ship.Speed, ship.Rate);
}
Console.WriteLine("\n=================================================================");
}
});
}
*/
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);
Console.Write("\nPress [q] to quit...");
do
{
}
while (Console.ReadKey().Key != ConsoleKey.Q);
}
private static Ship[] GetBestFleet3(IList<Voyage> voyages)
{
// 10771, 10779, 11103, 10859, 10742 ~ 10851
var bestRate = 0;
var worstVariance = 100.0;
Ship[] fleet = null;
foreach (var ship0 in voyages[0].Ships)
{
foreach (var ship1 in voyages[1].Ships.Where(s1 => !s1.Equals(ship0)))
{
foreach (var ship2 in voyages[2].Ships.Where(s2 => !s2.Equals(ship0) && !s2.Equals(ship1)))
{
var variance = Statistics.Variance(ship0, ship1, ship2);
var rate = ship0.Rate + ship1.Rate + ship2.Rate;
if (rate >= bestRate || rate == bestRate && variance < worstVariance)
{
bestRate = rate;
worstVariance = variance;
fleet = new[] {ship0, ship1, ship2};
if (ship0.Rate >= 100 && ship1.Rate >= 100 && ship2.Rate >= 100)
{
return fleet;
}
}
}
}
}
return fleet;
}
private static IEnumerable<IList<Ship>> PossibleVoyages(IList<Unit> rams, IList<Unit> decks, IList<Unit> hulls, IList<Unit> captains, IList<IList<Unit>> crews, int voyagesToPrepare, IList<Ship> fleet)
{
var possibleVoyages = new List<IList<Ship>>();
if (voyagesToPrepare == 0)
{
possibleVoyages.Add(fleet);
}
if (captains.Count < voyagesToPrepare || crews.Count < voyagesToPrepare)
{
// We cannot find any valid solution here
return possibleVoyages;
}
foreach (var ram in rams)
{
foreach (var deck1 in decks)
{
foreach (var deck2 in decks)
{
foreach (var hull in hulls)
{
foreach (var captain in captains)
{
foreach (var crew in crews)
{
fleet.Add(new Ship(ram, deck1, deck2, hull, captain, crew));
var newFleet = fleet;
possibleVoyages.AddRange(
PossibleVoyages(
rams, decks, hulls,
captains.Where(c => c != captain).ToList(),
crews.Where(c => c != crew).ToList(),
voyagesToPrepare - 1,
newFleet));
}
}
}
}
}
}
return possibleVoyages;
}
private static Ship[] GetBestFleet2(IList<Voyage> voyages)
{
var bestRate = 0;
var worstVariance = 100.0;
Ship[] fleet = null;
foreach (var ship0 in voyages[0].Ships)
{
foreach (var ship1 in voyages[1].Ships.Where(s1 => !s1.Equals(ship0)))
{
var variance = Statistics.Variance(ship0, ship1);
if (ship0.Rate + ship1.Rate > bestRate || ship0.Rate + ship1.Rate == bestRate && variance < worstVariance)
{
bestRate = ship0.Rate + ship1.Rate;
worstVariance = variance;
fleet = new[] { ship0, ship1 };
if (ship0.Rate >= 100 && ship1.Rate >= 100)
{
return fleet;
}
}
}
}
return fleet;
}
private static Ship[] GetBestFleet1(IList<Voyage> voyages)
{
if (voyages[0].Ships.Count == 0)
{
return null;
}
return new[] { voyages[0].Ships[0] };
}
private static IEnumerable<IList<T>> GetCombinationsWithoutRepetition<T>(IList<T> values, int lowerIndex)
{
foreach (IList<bool> permutation in new PermutationsWithoutRepetition<bool>(values.Select((t, i) => i < values.Count - lowerIndex)))
{
var list = new List<T>();
for (var i = 0; i < permutation.Count; i++)
{
if (!permutation[i])
{
list.Add(values[i]);
}
}
yield return list;
}
}
}
}
Raw
Ship.cs
using System;
using System.Collections.Generic;
using System.Threading;
namespace aLfPoP
{
internal class Ship : IEquatable<Ship>
{
private static readonly ThreadLocal<List<string>> _uniques = new ThreadLocal<List<string>>(() => new List<string>(5));
public Ship(Unit ram, Unit deck1, Unit deck2, Unit hull, Unit captain, IList<Unit> crew)
{
Ram = ram;
Deck1 = deck1;
Deck2 = deck2;
Hull = hull;
Captain = captain;
Crew = crew;
Morale = ram.Morale + deck1.Morale + deck2.Morale + hull.Morale + captain.Morale;
Combat = ram.Combat + deck1.Combat + deck2.Combat + hull.Combat + captain.Combat;
Seafar = ram.Seafar + deck1.Seafar + deck2.Seafar + hull.Seafar + captain.Seafar;
//Speed = ram.Speed + deck1.Speed + deck2.Speed + hull.Speed + captain.Speed;
const double moraleBonus = 1.03;
const double combatBonus = 1.03;
var seafaringBonus = 1.05;
//const double speedBonus = 1.03;
var uniques = _uniques.Value;
uniques.Clear();
var solidaryUnits = 0;
foreach (var unit in crew)
{
Morale += unit.Morale;
Combat += unit.Combat;
Seafar += unit.Seafar;
//Speed += unit.Speed;
if (!uniques.Contains(unit.Name))
{
uniques.Add(unit.Name);
}
if ((unit.Traits & Traits.Solidarity) != 0)
{
solidaryUnits += 1;
}
if ((unit.Traits & Traits.Seafriend) != 0)
{
seafaringBonus += 0.01;
}
}
if (solidaryUnits != 0)
{
var solidarityBonus = (uniques.Count + 1) * 100 * solidaryUnits;
Morale += solidarityBonus;
Combat += solidarityBonus;
Seafar += solidarityBonus;
}
Morale = (int) (moraleBonus * Morale);
Combat = (int) (combatBonus * Combat);
Seafar = (int) (seafaringBonus * Seafar);
//Speed = (int) (speedBonus * Speed);
}
public Unit Ram
{
get;
private set;
}
public Unit Deck1
{
get;
private set;
}
public Unit Deck2
{
get;
private set;
}
public Unit Hull
{
get;
private set;
}
public Unit Captain
{
get;
private set;
}
public IList<Unit> Crew
{
get;
private set;
}
public int Morale
{
get;
private set;
}
public int Combat
{
get;
private set;
}
public int Seafar
{
get;
private set;
}
public int Speed
{
get;
private set;
}
public int Rate
{
get;
internal set;
}
public bool Equals(Ship other)
{
if (ReferenceEquals(null, other))
{
return false;
}
if (ReferenceEquals(this, other))
{
return true;
}
if (Captain == other.Captain)
{
return true;
}
foreach (var member in Crew)
{
if (other.Crew.Contains(member))
{
return true;
}
}
return false;
}
public override bool Equals(object other)
{
return Equals(other as Ship);
}
public override int GetHashCode()
{
unchecked
{
var hashCode = Ram.GetHashCode();
hashCode = (hashCode * 397) ^ Deck1.GetHashCode();
hashCode = (hashCode * 397) ^ Deck2.GetHashCode();
hashCode = (hashCode * 397) ^ Hull.GetHashCode();
hashCode = (hashCode * 397) ^ Captain.GetHashCode();
hashCode = (hashCode * 397) ^ Crew.GetHashCode();
hashCode = (hashCode * 397) ^ Rate;
return hashCode;
}
}
}
}
Raw
ShipBase.cs
namespace aLfPoP
{
internal class ShipBase
{
public ShipBase(Unit ram, Unit deck1, Unit deck2, Unit hull)
{
Ram = ram;
Deck1 = deck1;
Deck2 = deck2;
Hull = hull;
Morale = ram.Morale + deck1.Morale + deck2.Morale + hull.Morale;
Combat = ram.Combat + deck1.Combat + deck2.Combat + hull.Combat;
Seafar = ram.Seafar + deck1.Seafar + deck2.Seafar + hull.Seafar;
Speed = ram.Speed + deck1.Speed + deck2.Speed + hull.Speed;
}
public Unit Ram
{
get;
private set;
}
public Unit Deck1
{
get;
private set;
}
public Unit Deck2
{
get;
private set;
}
public Unit Hull
{
get;
private set;
}
public int Morale
{
get;
private set;
}
public int Combat
{
get;
private set;
}
public int Seafar
{
get;
private set;
}
public int Speed
{
get;
private set;
}
public override string ToString()
{
return string.Format("\t{0}\t{1}\t{2}\t{3}", Morale, Combat, Seafar, Speed);
}
}
}
Raw
Statistics.cs
using System;
using System.Collections.Generic;
namespace aLfPoP
{
static class Statistics
{
public static double StdDev(this IEnumerable<double> values)
{
double mean = 0.0;
double sum = 0.0;
double stdDev = 0.0;
int n = 0;
foreach (double val in values)
{
n++;
double delta = val - mean;
mean += delta / n;
sum += delta * (val - mean);
}
if (1 < n)
stdDev = Math.Sqrt(sum / (n - 1));
return stdDev;
}
public static double StdDev(this IEnumerable<int> values)
{
double mean = 0.0;
double sum = 0.0;
double stdDev = 0.0;
int n = 0;
foreach (double val in values)
{
n++;
double delta = val - mean;
mean += delta / n;
sum += delta * (val - mean);
}
if (1 < n)
{
stdDev = Math.Sqrt(sum / n);
}
return stdDev;
}
public static double StdDev(this IEnumerable<Ship> ships)
{
double mean = 0.0;
double sum = 0.0;
double stdDev = 0.0;
int n = 0;
foreach (var ship in ships)
{
n++;
double delta = ship.Rate - mean;
mean += delta / n;
sum += delta * (ship.Rate - mean);
}
if (1 < n)
{
stdDev = Math.Sqrt(sum / n);
}
return stdDev;
}
public static double Variance(Ship ship0, Ship ship1)
{
double mean = (ship0.Rate + ship1.Rate) / 2.0;
return (ship0.Rate - mean) * (ship0.Rate - mean) + (ship1.Rate - mean) * (ship1.Rate - mean);
}
public static double Variance(Ship ship0, Ship ship1, Ship ship2)
{
double mean = (ship0.Rate + ship1.Rate + ship2.Rate) / 3.0;
return (ship0.Rate - mean) * (ship0.Rate - mean) + (ship1.Rate - mean) * (ship1.Rate - mean) + (ship2.Rate - mean) * (ship2.Rate - mean);
}
}
}
Raw
Traits.cs
using System;
namespace aLfPoP
{
[Flags]
internal enum Traits : long
{
None = 0x0,
Albatross = 0x1,
AweInspiring = 0x2,
Cowardly = 0x4,
Eager = 0x8,
EagleEyed = 0x10,
FastLearner = 0x20,
GoodFortune = 0x40,
Landlubber = 0x80,
Leader = 0x100,
Liability = 0x200,
Loyal = 0x400,
Merchant = 0x800,
MiseryGuts = 0x1000,
MultiTalented = 0x2000,
Mutinous = 0x4000,
Opportunist = 0x8000,
Pacifist = 0x10000,
Plucky = 0x20000,
QuickFooted = 0x40000,
RallyingCry = 0x80000,
Seafriend = 0x100000,
ShortSighted = 0x200000,
Slayer = 0x400000,
Solidarity = 0x800000,
Staunch = 0x1000000,
StormMagnet = 0x2000000,
Tactician = 0x4000000,
ToughAsNails = 0x8000000,
Workhorse = 0x10000000,
SlowWitted = 0x20000000,
Seafarer = 0x40000000,
Lookout = 0x80000000,
Resurrects = 0x100000000,
Vapid = 0x200000000
}
}
Raw
Unit.cs
namespace aLfPoP
{
internal class Unit
{
public Unit(int morale, int combat, int seafaring, int speed, int level, string name, Traits traits)
{
Morale = morale;
Combat = combat;
Seafar = seafaring;
Speed = speed;
Level = level;
Name = name;
Traits = traits;
}
public Unit(int morale, int combat, int seafaring, int speed, int level, string name)
: this(morale, combat, seafaring, speed, level, name, Traits.None)
{
}
public int Morale
{
get;
private set;
}
public int Combat
{
get;
private set;
}
public int Seafar
{
get;
private set;
}
public int Speed
{
get;
private set;
}
public int Level
{
get;
private set;
}
public string Name
{
get;
private set;
}
public Traits Traits
{
get;
private set;
}
public override string ToString()
{
return string.Format("{0}\t{1}\t{2}\t{3}\t{4} ({5})", Morale, Combat, Seafar, Speed, Name, Level);
}
}
}
Raw
Voyage.cs
using System;
using System.Collections.Generic;
using System.Linq;
using aLfPoP.Combinatorics;
namespace aLfPoP
{
internal class Voyage
{
public Voyage(int morale, int combat, int seafaring)
{
Morale = morale;
Combat = combat;
Seafar = seafaring;
}
public int Morale
{
get;
private set;
}
public int Combat
{
get;
private set;
}
public int Seafar
{
get;
private set;
}
public List<Ship> Ships
{
get;
set;
}
public IEnumerable<Ship> GetPossibleShips(int minimumRate, IList<Unit> rams, IList<Unit> decks, IList<Unit> hulls, IList<Unit> captains, IList<IList<Unit>> crews)
{
// get best ship base
IEnumerable<ShipBase> bestShipBases;
if (Combat == 1 && Seafar == 1)
{
// morale
bestShipBases = new[] { new ShipBase(rams[0], decks[0], decks[0], hulls[0]) };
}
else if (Morale == 1 && Seafar == 1)
{
// combat
bestShipBases = new[] { new ShipBase(rams[1], decks[1], decks[1], hulls[1]) };
}
else if (Morale == 1 && Combat == 1)
{
// seafaring
bestShipBases = new[] { new ShipBase(rams[0], decks[2], decks[2], hulls[2]) };
}
else if (Seafar == 1)
{
// morale + combat
bestShipBases = from ram in rams
from deckCombos in new Combinations<Unit>(new[] { decks[0], decks[1] }, 2, GenerateOption.WithRepetition)
from hull in new[] { hulls[0], hulls[1] }
select new ShipBase(ram, deckCombos[0], deckCombos[1], hull);
}
else if (Combat == 1)
{
// morale + seafaring
bestShipBases = from deckCombos in new Combinations<Unit>(new[] { decks[0], decks[2] }, 2, GenerateOption.WithRepetition)
from hull in new[] { hulls[0], hulls[2] }
select new ShipBase(rams[0], deckCombos[0], deckCombos[1], hull);
}
else if (Morale == 1)
{
// combat + seafaring
bestShipBases = from deckCombos in new Combinations<Unit>(new[] { decks[1], decks[2] }, 2, GenerateOption.WithRepetition)
from hull in new[] { hulls[1], hulls[2] }
select new ShipBase(rams[1], deckCombos[0], deckCombos[1], hull);
}
else
{
// morale + combat + seafaring
bestShipBases = from ram in rams
from deckCombos in new Combinations<Unit>(decks, 2, GenerateOption.WithRepetition)
from hull in hulls
select new ShipBase(ram, deckCombos[0], deckCombos[1], hull);
}
foreach (var shipBase in bestShipBases)
{
foreach (var captain in captains)
{
foreach (var crew in crews)
{
var ship = new Ship(shipBase.Ram, shipBase.Deck1, shipBase.Deck2, shipBase.Hull, captain, crew);
// calculate ship rating for this voyage
var rm = ship.Morale / Morale;
var rc = ship.Combat / Combat;
var rs = ship.Seafar / Seafar;
ship.Rate = rm > rc ? (rc > rs ? rs : rc) : (rm > rs ? rs : rm);
if (ship.Rate >= minimumRate && ship.Rate <= 100)
{
yield return ship;
}
}
}
}
}
public override string ToString()
{
return string.Format("Voyage ({0}, {1}, {2}) [{3}]", Morale, Combat, Seafar, Ships.Count);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment