Changeset 13953
 Timestamp:
 06/29/16 14:15:06 (6 years ago)
 Location:
 stable
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

stable
 Property svn:mergeinfo changed
/trunk/sources merged: 13802,13899
 Property svn:mergeinfo changed

stable/HeuristicLab.Common/3.3/EnumerableExtensions.cs
r12009 r13953 1 1 #region License Information 2 2 /* HeuristicLab 3 * Copyright (C) 2002201 5Heuristic and Evolutionary Algorithms Laboratory (HEAL)3 * Copyright (C) 20022016 Heuristic and Evolutionary Algorithms Laboratory (HEAL) 4 4 * 5 5 * This file is part of HeuristicLab. … … 98 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 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 long r = 1; 153 for (long d = 1; d <= k; d++) { 154 r *= n; 155 r /= d; 156 } 157 return r; 158 } 100 159 } 101 160 }
Note: See TracChangeset
for help on using the changeset viewer.