1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022016 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.Random {


28  public static class RandomEnumerable {


29  public static IEnumerable<int> SampleRandomNumbers(int maxElement, int count) {


30  return SampleRandomNumbers(Environment.TickCount, 0, maxElement, count);


31  }


32 


33  public static IEnumerable<int> SampleRandomNumbers(int start, int end, int count) {


34  return SampleRandomNumbers(Environment.TickCount, start, end, count);


35  }


36 


37  //algorithm taken from progamming pearls page 127


38  //IMPORTANT because IEnumerables with yield are used the seed must be specified to return always


39  //the same sequence of numbers without caching the values.


40  public static IEnumerable<int> SampleRandomNumbers(int seed, int start, int end, int count) {


41  int remaining = end  start;


42  var mt = new FastRandom(seed);


43  for (int i = start; i < end && count > 0; i++) {


44  double probability = mt.NextDouble();


45  if (probability < ((double)count) / remaining) {


46  count;


47  yield return i;


48  }


49  remaining;


50  }


51  }


52 


53  /// <summary>


54  /// Chooses one elements from a sequence giving each element an equal chance.


55  /// </summary>


56  /// <remarks>


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


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


59  /// </remarks>


60  /// <exception cref="ArgumentException">If the sequence is empty.</exception>


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


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


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


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


65  /// <returns>An element that has been chosen randomly from the sequence.</returns>


66  public static T SampleRandom<T>(this IEnumerable<T> source, IRandom random) {


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


68  return source.SampleRandom(random, 1).First();


69  }


70 


71  /// <summary>


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


73  /// </summary>


74  /// <remarks>


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


76  /// O(N * count) for all other. No exception is thrown if the sequence is empty.


77  ///


78  /// The method is online.


79  /// </remarks>


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


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


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


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


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


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


86  var listSource = source as IList<T>;


87  if (listSource != null) {


88  while (count > 0) {


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


90  count;


91  }


92  } else {


93  while (count > 0) {


94  var enumerator = source.GetEnumerator();


95  enumerator.MoveNext();


96  T selectedItem = enumerator.Current;


97  int counter = 1;


98  while (enumerator.MoveNext()) {


99  counter++;


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


101  selectedItem = enumerator.Current;


102  }


103  yield return selectedItem;


104  count;


105  }


106  }


107  }


108 


109  /// <summary>


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


111  /// The items are returned in the same order as they appear in the sequence.


112  /// </summary>


113  /// <remarks>


114  /// Runtime complexity is O(N) for all sequences.


115  /// No exception is thrown if the sequence contains less items than there are to be selected.


116  ///


117  /// The method is online.


118  /// </remarks>


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


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


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


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


123  /// <param name="sourceCount">Optional parameter specifying the number of elements in the source enumerations</param>


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


125  public static IEnumerable<T> SampleRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, int sourceCount = 1) {


126  if (sourceCount == 1) sourceCount = source.Count();


127  int remaining = sourceCount;


128  foreach (var item in source) {


129  if (random.NextDouble() * remaining < count) {


130  count;


131  yield return item;


132  if (count <= 0) break;


133  }


134  remaining;


135  }


136  }


137 


138  /// <summary>


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


140  /// to the <paramref name="weights"/>.


141  /// </summary>


142  /// <remarks>


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


144  /// otherwise an InvalidOperationException is thrown.


145  ///


146  /// The method internally holds two arrays: One that is the sequence itself and another one for the values.


147  /// </remarks>


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


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


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


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


152  /// <param name="weights">The weight values for the items.</param>


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


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


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


156  public static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, IRandom random, int count, IEnumerable<double> weights, bool windowing = true, bool inverseProportional = false) {


157  return source.SampleProportional(random, weights, windowing, inverseProportional).Take(count);


158  }


159 


160  /// <summary>


161  /// Same as <seealso cref="SampleProportional<T>"/>, but chooses an item exactly once.


162  /// </summary>


163  /// <remarks>


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


165  /// otherwise an InvalidOperationException is thrown.


166  ///


167  /// The method internally holds two arrays: One that is the sequence itself and another one for the values.


168  ///


169  /// The method does not check if the number of elements in source and weights are the same.


170  /// </remarks>


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


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


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


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


175  /// <param name="weights">The weight values for the items.</param>


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


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


178  /// <returns>A sequence of selected items. Might actually be shorter than <paramref name="count"/> elements if source has less than <paramref name="count"/> elements.</returns>


179  public static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, IEnumerable<double> weights, bool windowing = true, bool inverseProportional = false) {


180  return source.SampleProportionalWithoutRepetition(random, weights, windowing, inverseProportional).Take(count);


181  }


182  #region Proportional Helpers


183  private static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {


184  var sourceArray = source.ToArray();


185  var valueArray = PrepareProportional(weights, windowing, inverseProportional);


186  double total = valueArray.Sum();


187 


188  while (true) {


189  int index = 0;


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


191  while (ball < sum)


192  ball += valueArray[++index];


193  yield return sourceArray[index];


194  }


195  }


196  private static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {


197  var valueArray = PrepareProportional(weights, windowing, inverseProportional);


198  var list = new LinkedList<Tuple<T, double>>(source.Zip(valueArray, Tuple.Create));


199  double total = valueArray.Sum();


200 


201  while (list.Count > 0) {


202  var cur = list.First;


203  double ball = cur.Value.Item2, sum = random.NextDouble() * total; // assert: sum < total. When there is only one item remaining: sum < ball


204  while (ball < sum) {


205  cur = cur.Next;


206  ball += cur.Value.Item2;


207  }


208  yield return cur.Value.Item1;


209  list.Remove(cur);


210  total = cur.Value.Item2;


211  }


212  }


213 


214  private static double[] PrepareProportional(IEnumerable<double> weights, bool windowing, bool inverseProportional) {


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


216  double[] valueArray = weights.ToArray();


217 


218  for (int i = 0; i < valueArray.Length; i++) {


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


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


221  }


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


223  for (int i = 0; i < valueArray.Length; i++) {


224  valueArray[i] = 1.0;


225  }


226  } else {


227  if (windowing) {


228  if (inverseProportional) InverseProportionalScale(valueArray, maxValue);


229  else ProportionalScale(valueArray, minValue);


230  } else {


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


232  if (inverseProportional) InverseProportionalScale(valueArray, 2 * maxValue);


233  }


234  }


235  return valueArray;


236  }


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


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


239  values[i] = values[i]  minValue;


240  }


241  }


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


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


244  values[i] = maxValue  values[i];


245  }


246  }


247  #endregion


248 


249  /// <summary>


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


251  /// </summary>


252  /// <remarks>


253  /// Note that the source enumerable is transformed into an array.


254  ///


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


256  /// </remarks>


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


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


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


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


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


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


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


264  // Swap element "i" with a random earlier element (including itself)


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


266  yield return elements[swapIndex];


267  elements[swapIndex] = elements[i];


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


269  // swapped element because we already returned it.


270  }


271  if (elements.Length > 0)


272  yield return elements[0];


273  }


274  }


275  }


276 

