1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022013 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(sourceArray, 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(source.ToArray(), 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<T>(IList<T> sourceArray, IEnumerable<double> weights, bool windowing, bool inverseProportional) {


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


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


217 


218  var weightsEnum = weights.GetEnumerator();


219  for (int i = 0; i < sourceArray.Count && weightsEnum.MoveNext(); i++) {


220  valueArray[i] = weightsEnum.Current;


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


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


223  }


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


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


226  valueArray[i] = 1.0;


227  }


228  } else {


229  if (windowing) {


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


231  else ProportionalScale(valueArray, minValue);


232  } else {


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


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


235  }


236  }


237  return valueArray;


238  }


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


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


241  values[i] = values[i]  minValue;


242  }


243  }


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


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


246  values[i] = maxValue  values[i];


247  }


248  }


249  #endregion


250 


251  /// <summary>


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


253  /// </summary>


254  /// <remarks>


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


256  ///


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


258  /// </remarks>


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


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


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


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


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


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


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


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


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


268  yield return elements[swapIndex];


269  elements[swapIndex] = elements[i];


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


271  // swapped element because we already returned it.


272  }


273  yield return elements[0];


274  }


275  }


276  }


277 

