[5484] | 1 | #region License Information |
---|
| 2 | /* HeuristicLab |
---|
[16565] | 3 | * Copyright (C) 2002-2019 Heuristic and Evolutionary Algorithms Laboratory (HEAL) |
---|
[5484] | 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; |
---|
[7812] | 24 | using System.Linq; |
---|
| 25 | using HeuristicLab.Core; |
---|
[5484] | 26 | |
---|
| 27 | namespace HeuristicLab.Random { |
---|
[7812] | 28 | public static class RandomEnumerable { |
---|
[5484] | 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 |
---|
[10466] | 38 | //IMPORTANT because IEnumerables with yield are used the seed must be specified to return always |
---|
[5484] | 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 | } |
---|
[7812] | 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> |
---|
[9072] | 123 | /// <param name="sourceCount">Optional parameter specifying the number of elements in the source enumerations</param> |
---|
[7812] | 124 | /// <returns>A sequence of elements that have been chosen randomly.</returns> |
---|
[9072] | 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; |
---|
[7812] | 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 inverse-proportional |
---|
| 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 inverse-proportionally (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. |
---|
[10466] | 168 | /// |
---|
| 169 | /// The method does not check if the number of elements in source and weights are the same. |
---|
[7812] | 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> |
---|
[10466] | 177 | /// <param name="inverseProportional">Determines whether to choose proportionally (true) or inverse-proportionally (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> |
---|
[7812] | 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(); |
---|
[10503] | 185 | var valueArray = PrepareProportional(weights, windowing, inverseProportional); |
---|
[7812] | 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) { |
---|
[10503] | 197 | var valueArray = PrepareProportional(weights, windowing, inverseProportional); |
---|
[10466] | 198 | var list = new LinkedList<Tuple<T, double>>(source.Zip(valueArray, Tuple.Create)); |
---|
[7812] | 199 | double total = valueArray.Sum(); |
---|
| 200 | |
---|
[10503] | 201 | while (list.Count > 0) { |
---|
| 202 | var cur = list.First; |
---|
[10466] | 203 | double ball = cur.Value.Item2, sum = random.NextDouble() * total; // assert: sum < total. When there is only one item remaining: sum < ball |
---|
[16496] | 204 | while (ball < sum && cur.Next != null) { |
---|
[10466] | 205 | cur = cur.Next; |
---|
| 206 | ball += cur.Value.Item2; |
---|
[7812] | 207 | } |
---|
[10466] | 208 | yield return cur.Value.Item1; |
---|
| 209 | list.Remove(cur); |
---|
| 210 | total -= cur.Value.Item2; |
---|
[7812] | 211 | } |
---|
| 212 | } |
---|
[10466] | 213 | |
---|
[10503] | 214 | private static double[] PrepareProportional(IEnumerable<double> weights, bool windowing, bool inverseProportional) { |
---|
[7812] | 215 | double maxValue = double.MinValue, minValue = double.MaxValue; |
---|
[10503] | 216 | double[] valueArray = weights.ToArray(); |
---|
[7812] | 217 | |
---|
[10503] | 218 | for (int i = 0; i < valueArray.Length; i++) { |
---|
[7812] | 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 |
---|
[10503] | 223 | for (int i = 0; i < valueArray.Length; i++) { |
---|
[7812] | 224 | valueArray[i] = 1.0; |
---|
| 225 | } |
---|
| 226 | } else { |
---|
| 227 | if (windowing) { |
---|
[7828] | 228 | if (inverseProportional) InverseProportionalScale(valueArray, maxValue); |
---|
| 229 | else ProportionalScale(valueArray, minValue); |
---|
[7812] | 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 Fisher-Yates 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/c-is-using-random-and-orderby-a-good-shuffle-algorithm. |
---|
| 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 | } |
---|
[14522] | 271 | if (elements.Length > 0) |
---|
| 272 | yield return elements[0]; |
---|
[7812] | 273 | } |
---|
[5484] | 274 | } |
---|
| 275 | } |
---|
[10466] | 276 | |
---|