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.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 best 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  /// <returns>A sequence of elements that have been chosen randomly.</returns>


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


125  int remaining = source.Count();


126  foreach (var item in source) {


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


128  count;


129  yield return item;


130  if (count <= 0) break;


131  }


132  remaining;


133  }


134  }


135 


136  /// <summary>


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


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


139  /// </summary>


140  /// <remarks>


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


142  /// otherwise an InvalidOperationException is thrown.


143  ///


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


145  /// </remarks>


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


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


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


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


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


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


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


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


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


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


156  }


157 


158  /// <summary>


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


160  /// </summary>


161  /// <remarks>


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


163  /// otherwise an InvalidOperationException is thrown.


164  ///


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


166  /// </remarks>


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


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


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


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


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


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


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


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


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


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


177  }


178  #region Proportional Helpers


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


180  var sourceArray = source.ToArray();


181  var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);


182  double total = valueArray.Sum();


183 


184  while (true) {


185  int index = 0;


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


187  while (ball < sum)


188  ball += valueArray[++index];


189  yield return sourceArray[index];


190  }


191  }


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


193  var sourceArray = source.ToArray();


194  var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);


195  double total = valueArray.Sum();


196 


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


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


199  int index = 0;


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


201  while (ball < sum) {


202  index++;


203  if (!chosenIndices.Contains(index))


204  ball += valueArray[++index];


205  }


206  yield return sourceArray[index];


207  chosenIndices.Add(index);


208  total = valueArray[index];


209  }


210  }


211  private static double[] PrepareProportional<T>(IList<T> sourceArray, IEnumerable<double> weights, bool windowing, bool inverseProportional) {


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


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


214 


215  var weightsEnum = weights.GetEnumerator();


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


217  valueArray[i] = weightsEnum.Current;


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


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


220  }


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


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


223  valueArray[i] = 1.0;


224  }


225  } else {


226  if (windowing) {


227  if (inverseProportional) InverseProportionalScale(valueArray, minValue);


228  else ProportionalScale(valueArray, maxValue);


229  } else {


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


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


232  }


233  }


234  return valueArray;


235  }


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


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


238  values[i] = values[i]  minValue;


239  }


240  }


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


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


243  values[i] = maxValue  values[i];


244  }


245  }


246  #endregion


247 


248  /// <summary>


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


250  /// </summary>


251  /// <remarks>


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


253  ///


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


255  /// </remarks>


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


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


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


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


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


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


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


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


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


265  yield return elements[swapIndex];


266  elements[swapIndex] = elements[i];


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


268  // swapped element because we already returned it.


269  }


270  yield return elements[0];


271  }


272  }


273  }

