Changeset 10466
 Timestamp:
 02/19/14 11:30:23 (10 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/sources/HeuristicLab.Random/3.3/RandomEnumerable.cs
r10407 r10466 36 36 37 37 //algorithm taken from progamming pearls page 127 38 //IMPORTANT because IEnumerables with yield are used the seed must be st bespecified to return always38 //IMPORTANT because IEnumerables with yield are used the seed must be specified to return always 39 39 //the same sequence of numbers without caching the values. 40 40 public static IEnumerable<int> SampleRandomNumbers(int seed, int start, int end, int count) { … … 166 166 /// 167 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. 168 170 /// </remarks> 169 171 /// <typeparam name="T">The type of the items to be selected.</typeparam> … … 173 175 /// <param name="weights">The weight values for the items.</param> 174 176 /// <param name="windowing">Whether to scale the proportional values or not.</param> 175 /// <param name=" maximization">Determines whether to choose proportionally (true) or inverseproportionally (false).</param>176 /// <returns>A sequence of selected items. </returns>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> 177 179 public static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, IEnumerable<double> weights, bool windowing = true, bool inverseProportional = false) { 178 180 return source.SampleProportionalWithoutRepetition(random, weights, windowing, inverseProportional).Take(count); … … 181 183 private static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) { 182 184 var sourceArray = source.ToArray(); 183 var valueArray = PrepareProportional <T>(sourceArray, weights, windowing, inverseProportional);185 var valueArray = PrepareProportional(sourceArray, weights, windowing, inverseProportional); 184 186 double total = valueArray.Sum(); 185 187 … … 193 195 } 194 196 private static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) { 195 var sourceArray = source.ToArray();196 var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);197 var valueArray = PrepareProportional(source.ToArray(), weights, windowing, inverseProportional); 198 var list = new LinkedList<Tuple<T, double>>(source.Zip(valueArray, Tuple.Create)); 197 199 double total = valueArray.Sum(); 198 200 199 HashSet<int> chosenIndices = new HashSet<int>(); 200 while (chosenIndices.Count < sourceArray.Length) { 201 int index = 1; 202 double ball = 0, sum = random.NextDouble() * total; 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 203 204 while (ball < sum) { 204 index++; 205 if (!chosenIndices.Contains(index)) 206 ball += valueArray[index]; 207 } 208 index = index >= 0 ? index : Enumerable.Range(0, sourceArray.Length).First(x => !chosenIndices.Contains(x)); 209 yield return sourceArray[index]; 210 chosenIndices.Add(index); 211 total = valueArray[index]; 212 } 213 } 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 214 private static double[] PrepareProportional<T>(IList<T> sourceArray, IEnumerable<double> weights, bool windowing, bool inverseProportional) { 215 215 double maxValue = double.MinValue, minValue = double.MaxValue; … … 275 275 } 276 276 } 277
Note: See TracChangeset
for help on using the changeset viewer.