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 


26  namespace HeuristicLab.Common {


27  public static class EnumerableExtensions {


28  /// <summary>


29  /// Selects all elements in the sequence that are maximal with respect to the given value.


30  /// </summary>


31  /// <remarks>


32  /// Runtime complexity of the operation is O(N).


33  /// </remarks>


34  /// <typeparam name="T">The type of the elements.</typeparam>


35  /// <param name="source">The enumeration in which the items with a maximal value should be found.</param>


36  /// <param name="valueSelector">The function that selects the value to compare.</param>


37  /// <returns>All elements in the enumeration where the selected value is the maximum.</returns>


38  public static IEnumerable<T> MaxItems<T>(this IEnumerable<T> source, Func<T, IComparable> valueSelector) {


39  IEnumerator<T> enumerator = source.GetEnumerator();


40  if (!enumerator.MoveNext()) return Enumerable.Empty<T>();


41  IComparable max = valueSelector(enumerator.Current);


42  var result = new List<T>();


43  result.Add(enumerator.Current);


44 


45  while (enumerator.MoveNext()) {


46  T item = enumerator.Current;


47  IComparable comparison = valueSelector(item);


48  if (comparison.CompareTo(max) > 0) {


49  result.Clear();


50  result.Add(item);


51  max = comparison;


52  } else if (comparison.CompareTo(max) == 0) {


53  result.Add(item);


54  }


55  }


56  return result;


57  }


58 


59  /// <summary>


60  /// Selects all elements in the sequence that are minimal with respect to the given value.


61  /// </summary>


62  /// <remarks>


63  /// Runtime complexity of the operation is O(N).


64  /// </remarks>


65  /// <typeparam name="T">The type of the elements.</typeparam>


66  /// <param name="source">The enumeration in which items with a minimal value should be found.</param>


67  /// <param name="valueSelector">The function that selects the value.</param>


68  /// <returns>All elements in the enumeration where the selected value is the minimum.</returns>


69  public static IEnumerable<T> MinItems<T>(this IEnumerable<T> source, Func<T, IComparable> valueSelector) {


70  IEnumerator<T> enumerator = source.GetEnumerator();


71  if (!enumerator.MoveNext()) return Enumerable.Empty<T>();


72  IComparable min = valueSelector(enumerator.Current);


73  var result = new List<T>();


74  result.Add(enumerator.Current);


75 


76  while (enumerator.MoveNext()) {


77  T item = enumerator.Current;


78  IComparable comparison = valueSelector(item);


79  if (comparison.CompareTo(min) < 0) {


80  result.Clear();


81  result.Add(item);


82  min = comparison;


83  } else if (comparison.CompareTo(min) == 0) {


84  result.Add(item);


85  }


86  }


87  return result;


88  }


89 


90  /// <summary>


91  /// Compute the nary cartesian product of arbitrarily many sequences: http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computingacartesianproductwithlinq.aspx


92  /// </summary>


93  /// <typeparam name="T">The type of the elements inside each sequence</typeparam>


94  /// <param name="sequences">The collection of sequences</param>


95  /// <returns>An enumerable sequence of all the possible combinations of elements</returns>


96  public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) {


97  IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };


98  return sequences.Where(s => s.Any()).Aggregate(result, (current, s) => (from seq in current from item in s select seq.Concat(new[] { item })));


99  }


100 


101  /// <summary>


102  /// Compute all kcombinations of elements from the provided collection.


103  /// <param name="elements">The collection of elements</param>


104  /// <param name="k">The combination group size</param>


105  /// <returns>An enumerable sequence of all the possible kcombinations of elements</returns>


106  /// </summary>


107  public static IEnumerable<IEnumerable<T>> Combinations<T>(this IList<T> elements, int k) {


108  if (k > elements.Count)


109  throw new ArgumentException();


110 


111  if (k == 1) {


112  foreach (var element in elements)


113  yield return new[] { element };


114  yield break;


115  }


116 


117  int n = elements.Count;


118  var range = Enumerable.Range(0, k).ToArray();


119  var length = BinomialCoefficient(n, k);


120 


121  for (int i = 0; i < length; ++i) {


122  yield return range.Select(x => elements[x]);


123 


124  if (i == length  1) break;


125  var m = k  1;


126  var max = n  1;


127 


128  while (range[m] == max) { m; max; }


129  range[m]++;


130  for (int j = m + 1; j < k; ++j) {


131  range[j] = range[j  1] + 1;


132  }


133  }


134  }


135 


136  /// <summary>


137  /// This function gets the total number of unique combinations based upon N and K,


138  /// where N is the total number of items and K is the size of the group.


139  /// It calculates the total number of unique combinations C(N, K) = N! / ( K! (N  K)! )


140  /// using the recursion C(N+1, K+1) = (N+1 / K+1) * C(N, K).


141  /// <remarks>http://blog.plover.com/math/choose.html</remarks>


142  /// <remark>https://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula</remark>


143  /// <param name="n">The number of elements</param>


144  /// <param name="k">The size of the group</param>


145  /// <returns>The binomial coefficient C(N, K)</returns>


146  /// </summary>


147  public static long BinomialCoefficient(long n, long k) {


148  if (k > n) return 0;


149  if (k == n) return 1;


150  if (k > n  k)


151  k = n  k;


152 


153  // enable explicit overflow checking for very large coefficients


154  checked {


155  long r = 1;


156  for (long d = 1; d <= k; d++) {


157  r *= n;


158  r /= d;


159  }


160  return r;


161  }


162  }


163  }


164  }

