1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HeuristicLab.Core;


26 


27  namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common {


28  public static class ExtensionMethods {


29 


30  #region Choosing from a sequence


31  /// <summary>


32  /// Chooses one elements from a sequence under equal chances for each element.


33  /// </summary>


34  /// <remarks>


35  /// Runtime complexity is O(1) for sequences that are <see cref="IList{T}"/> and


36  /// O(N) for all other.


37  /// </remarks>


38  /// <typeparam name="T">The type of the items to be selected.</typeparam>


39  /// <param name="source">The sequence of elements.</param>


40  /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>


41  /// <param name="count">The number of items to be selected.</param>


42  /// <returns>A sequence of elements that have been chosen randomly.</returns>


43  public static T ChooseUniformRandom<T>(this IEnumerable<T> source, IRandom random) {


44  return source.ChooseUniformRandom(random, 1).First();


45  }


46  /// <summary>


47  /// Chooses <paramref name="count"/> elements from a sequence with repetition under equal chances for each element.


48  /// </summary>


49  /// <remarks>


50  /// Runtime complexity is O(count) for sequences that are <see cref="IList{T}"/> and


51  /// O(N * count) for all other.


52  ///


53  /// The method is online.


54  /// </remarks>


55  /// <typeparam name="T">The type of the items to be selected.</typeparam>


56  /// <param name="source">The sequence of elements.</param>


57  /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>


58  /// <param name="count">The number of items to be selected.</param>


59  /// <returns>A sequence of elements that have been chosen randomly.</returns>


60  public static IEnumerable<T> ChooseUniformRandom<T>(this IEnumerable<T> source, IRandom random, int count) {


61  if (source == null) throw new ArgumentNullException("source", "sequence is null");


62  if (!source.Any()) throw new ArgumentException("sequence is empty.", "source");


63 


64  var listSource = source as IList<T>;


65  if (listSource != null)


66  while (count > 0) {


67  yield return listSource[random.Next(listSource.Count)];


68  count;


69  }


70 


71  while (count > 0) {


72  var enumerator = source.GetEnumerator();


73  enumerator.MoveNext();


74  T selectedItem = enumerator.Current;


75  int counter = 1;


76  while (enumerator.MoveNext()) {


77  counter++;


78  if (counter * random.NextDouble() < 1.0)


79  selectedItem = enumerator.Current;


80  }


81  yield return selectedItem;


82  count;


83  }


84  }


85  /// <summary>


86  /// Chooses <paramref name="count"/> elements from a sequence without repetition under equal chances for each element.


87  /// </summary>


88  /// <remarks>


89  /// Runtime complexity is O(count) for sequences that are <see cref="IList{T}"/> and


90  /// O(N * count) for all other.


91  ///


92  /// The method is online, but the source enumerable is transformed into an array.


93  /// </remarks>


94  /// <typeparam name="T">The type of the items to be selected.</typeparam>


95  /// <param name="source">The sequence of elements.</param>


96  /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>


97  /// <param name="count">The number of items to be selected.</param>


98  /// <returns>A sequence of elements that have been chosen randomly.</returns>


99  public static IEnumerable<T> ChooseUniformRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count) {


100  return source.Shuffle(random).Take(count);


101  }


102 


103  /// <summary>


104  /// Chooses items out of a sequence with repetition. The chance that an item is selected is proportional or inverseproportional


105  /// to the value obtained from <paramref name="valueSelector"/>.


106  /// </summary>


107  /// <remarks>


108  /// In case both <paramref name="maximization"/> and <paramref name="windowing"/> are false values must be > 0,


109  /// otherwise an InvalidOperationException is thrown.


110  ///


111  /// The method is online, but internally holds two arrays: One that is the sequence itself and another one for the values. The <paramref name="valueSelector"/>


112  /// is only applied once for each item.


113  /// </remarks>


114  /// <typeparam name="T">The type of the items to be selected.</typeparam>


115  /// <param name="source">The sequence of elements.</param>


116  /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>


117  /// <param name="count">The number of items to be selected.</param>


118  /// <param name="valueSelector">The function that calculates a proportional value for each item.</param>


119  /// <param name="windowing">Whether to scale the proportional values or not.</param>


120  /// <param name="maximization">Determines whether to choose proportionally (true) or inverseproportionally (false).</param>


121  /// <returns>A sequence of selected items. The sequence might contain the same item more than once.</returns>


122  public static IEnumerable<T> ChooseProportionalRandom<T>(this IEnumerable<T> source, IRandom random, int count, Func<T, double> valueSelector, bool windowing, bool maximization) {


123  return source.ChooseProportionalRandom(random, valueSelector, windowing, maximization).Take(count);


124  }


125  /// <summary>


126  /// Same as <seealso cref="ChooseProportionalRandom<T>"/>, but selects each item exactly once.


127  /// </summary>


128  /// <remarks>


129  /// In case both <paramref name="maximization"/> and <paramref name="windowing"/> are false values must be > 0,


130  /// otherwise an InvalidOperationException is thrown.


131  ///


132  /// The method is online, but internally holds two arrays: One that is the sequence itself and another one for the values. The <paramref name="valueSelector"/>


133  /// is only applied once for each item.


134  /// </remarks>


135  /// <typeparam name="T">The type of the items to be selected.</typeparam>


136  /// <param name="source">The sequence of elements.</param>


137  /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>


138  /// <param name="count">The number of items to be selected.</param>


139  /// <param name="valueSelector">The function that calculates a proportional value for each item.</param>


140  /// <param name="windowing">Whether to scale the proportional values or not.</param>


141  /// <param name="maximization">Determines whether to choose proportionally (true) or inverseproportionally (false).</param>


142  /// <returns>A sequence of selected items.</returns>


143  public static IEnumerable<T> ChooseProportionalRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, Func<T, double> valueSelector, bool windowing, bool maximization) {


144  return source.ChooseProportionalRandomWithoutRepetition(random, valueSelector, windowing, maximization).Take(count);


145  }


146  #region Proportional Helpers


147  private static IEnumerable<T> ChooseProportionalRandom<T>(this IEnumerable<T> source, IRandom random, Func<T, double> valueSelector, bool windowing, bool maximization) {


148  if (source == null) throw new ArgumentNullException("source", "sequence is null");


149  if (!source.Any()) throw new ArgumentException("sequence is empty.", "source");


150 


151  var sourceArray = source.ToArray();


152  var valueArray = PrepareProportional<T>(sourceArray, valueSelector, windowing, maximization);


153  double total = valueArray.Sum();


154 


155  while (true) {


156  int index = 0;


157  double ball = valueArray[index], sum = random.NextDouble() * total;


158  while (ball < sum)


159  ball += valueArray[++index];


160  yield return sourceArray[index];


161  }


162  }


163  private static IEnumerable<T> ChooseProportionalRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, Func<T, double> valueSelector, bool windowing, bool maximization) {


164  if (source == null) throw new ArgumentNullException("source", "sequence is null");


165  if (!source.Any()) throw new ArgumentException("sequence is empty.", "source");


166 


167  var sourceArray = source.ToArray();


168  var valueArray = PrepareProportional<T>(sourceArray, valueSelector, windowing, maximization);


169  double total = valueArray.Sum();


170 


171  HashSet<int> chosenIndices = new HashSet<int>();


172  while (chosenIndices.Count < sourceArray.Length) {


173  int index = 0;


174  double ball = valueArray[index], sum = random.NextDouble() * total;


175  while (ball < sum) {


176  index++;


177  if (!chosenIndices.Contains(index))


178  ball += valueArray[++index];


179  }


180  yield return sourceArray[index];


181  chosenIndices.Add(index);


182  total = valueArray[index];


183  }


184  }


185  private static double[] PrepareProportional<T>(IList<T> sourceArray, Func<T, double> valueSelector, bool windowing, bool maximization) {


186  double maxValue = double.MinValue, minValue = double.MaxValue;


187  double[] valueArray = new double[sourceArray.Count];


188 


189  for (int i = 0; i < sourceArray.Count; i++) {


190  valueArray[i] = valueSelector(sourceArray[i]);


191  if (valueArray[i] > maxValue) maxValue = valueArray[i];


192  if (valueArray[i] < minValue) minValue = valueArray[i];


193  }


194  if (minValue == maxValue) { // all values are equal


195  for (int i = 0; i < sourceArray.Count; i++) {


196  valueArray[i] = 1.0;


197  }


198  } else {


199  if (windowing) {


200  if (maximization) ProportionalScale(valueArray, minValue);


201  else InverseProportionalScale(valueArray, maxValue);


202  } else {


203  if (minValue < 0.0) throw new InvalidOperationException("Proportional selection without windowing does not work with values < 0.");


204  if (!maximization) InverseProportionalScale(valueArray, 2 * maxValue);


205  }


206  }


207  return valueArray;


208  }


209  private static void ProportionalScale(double[] values, double minValue) {


210  for (int i = 0; i < values.Length; i++) {


211  values[i] = values[i]  minValue;


212  }


213  }


214  private static void InverseProportionalScale(double[] values, double maxValue) {


215  for (int i = 0; i < values.Length; i++) {


216  values[i] = maxValue  values[i];


217  }


218  }


219  #endregion


220 


221  /// <summary>


222  /// Selects the first element in the sequence where the selected key is the maximum.


223  /// </summary>


224  /// <remarks>


225  /// Runtime complexity of the operation is O(N).


226  /// </remarks>


227  /// <typeparam name="T">The type of the elements.</typeparam>


228  /// <typeparam name="TComparable">The selected key (needs to be an IComparable).</typeparam>


229  /// <param name="source">The enumeration in which the maximum item should be found.</param>


230  /// <param name="keySelector">The function that selects the key.</param>


231  /// <returns>The element in the enumeration where the selected key is the maximum.</returns>


232  public static T ChooseMax<T, TComparable>(this IEnumerable<T> source, Func<T, TComparable> keySelector) where TComparable : IComparable {


233  if (source == null) throw new ArgumentNullException("source", "sequence is null");


234  IEnumerator<T> enumerator = source.GetEnumerator();


235  if (!enumerator.MoveNext()) throw new ArgumentException("sequence is empty", "source");


236  T result = enumerator.Current;


237  TComparable max = keySelector(result);


238  while (enumerator.MoveNext()) {


239  T item = enumerator.Current;


240  TComparable comparison = keySelector(item);


241  if (comparison.CompareTo(max) > 0) {


242  result = item;


243  max = comparison;


244  }


245  }


246  return result;


247  }


248 


249  /// <summary>


250  /// Selects the first element in the sequence where the selected key is the minimum.


251  /// </summary>


252  /// <remarks>


253  /// Runtime complexity of the operation is O(N).


254  /// </remarks>


255  /// <typeparam name="T">The type of the elements.</typeparam>


256  /// <typeparam name="TComparable">The selected key (needs to be an IComparable).</typeparam>


257  /// <param name="source">The enumeration in which the minimum item should be found.</param>


258  /// <param name="keySelector">The function that selects the key.</param>


259  /// <returns>The element in the enumeration where the selected key is the minimum.</returns>


260  public static T ChooseMin<T, TComparable>(this IEnumerable<T> source, Func<T, TComparable> keySelector) where TComparable : IComparable {


261  if (source == null) throw new ArgumentNullException("source", "sequence is null");


262  IEnumerator<T> enumerator = source.GetEnumerator();


263  if (!enumerator.MoveNext()) throw new ArgumentException("sequence is empty", "source");


264  T result = enumerator.Current;


265  TComparable min = keySelector(result);


266  while (enumerator.MoveNext()) {


267  T item = enumerator.Current;


268  TComparable comparison = keySelector(item);


269  if (comparison.CompareTo(min) < 0) {


270  result = item;


271  min = comparison;


272  }


273  }


274  return result;


275  }


276  #endregion


277 


278  #region Shuffling


279  /// <summary>


280  /// Shuffles an enumerable and returns a new enumerable according to the FisherYates shuffle.


281  /// </summary>


282  /// <remarks>


283  /// Note that this is an online shuffle, but the source enumerable is transformed into an array.


284  ///


285  /// The implementation is described in http://stackoverflow.com/questions/1287567/cisusingrandomandorderbyagoodshufflealgorithm.


286  /// </remarks>


287  /// <typeparam name="T">The type of the items that are to be shuffled.</typeparam>


288  /// <param name="source">The enumerable that contains the items.</param>


289  /// <param name="random">The random number generator, its Next(n) method must deliver uniformly distributed random numbers in the range [0;n).</param>


290  /// <returns>An enumerable with the elements shuffled.</returns>


291  public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, IRandom random) {


292  T[] elements = source.ToArray();


293  for (int i = elements.Length  1; i > 0; i) {


294  // Swap element "i" with a random earlier element it (or itself)


295  int swapIndex = random.Next(i + 1);


296  yield return elements[swapIndex];


297  elements[swapIndex] = elements[i];


298  // we don't actually perform the swap, we can forget about the


299  // swapped element because we already returned it.


300  }


301  yield return elements[0];


302  }


303  #endregion


304 


305  #region Graph walk


306  /// <summary>


307  /// Walks an operator graph in that it jumps from one operator to all its operator parameters and yields each operator it touches.


308  /// Cycles are detected and not walked twice.


309  /// </summary>


310  /// <param name="initial">The operator where the walk starts (is also yielded).</param>


311  /// <returns>An enumeration of all the operators that could be found.</returns>


312  public static IEnumerable<IOperator> Walk(this IOperator initial) {


313  var open = new Stack<IOperator>();


314  var visited = new HashSet<IOperator>();


315  open.Push(initial);


316 


317  while (open.Any()) {


318  IOperator current = open.Pop();


319  if (visited.Contains(current)) continue;


320  visited.Add(current);


321 


322  foreach (var parameter in current.Parameters.OfType<IValueParameter>()) {


323  if (typeof(IOperator).IsAssignableFrom(parameter.DataType)) {


324  if (parameter.Value != null)


325  open.Push((IOperator)parameter.Value);


326  }


327  }


328 


329  yield return current;


330  }


331  }


332  #endregion


333 


334  #region Matrix operations


335  public static double[,] Transpose(this double[,] matrix) {


336  var result = new double[matrix.GetLength(1), matrix.GetLength(0)];


337  for (int i = 0; i < matrix.GetLength(0); i++)


338  for (int j = 0; j < matrix.GetLength(1); j++)


339  result[j, i] = matrix[i, j];


340  return result;


341  }


342  #endregion


343  }


344  }

