Changeset 13899 for trunk/sources/HeuristicLab.Common/3.3
- Timestamp:
- 06/16/16 15:33:47 (8 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.Common/3.3/EnumerableExtensions.cs
r13802 r13899 108 108 if (k > elements.Count) 109 109 throw new ArgumentException(); 110 110 111 if (k == 1) { 111 foreach(var element in elements) yield return new[] { element }; 112 } else { 113 int n = elements.Count; 114 var range = new int[k]; 115 for (int i = 1; i < k; ++i) 116 range[i] = i; 112 foreach (var element in elements) 113 yield return new[] { element }; 114 yield break; 115 } 117 116 118 var length = BinomialCoefficient(n, k); 117 int n = elements.Count; 118 var range = Enumerable.Range(0, k).ToArray(); 119 var length = BinomialCoefficient(n, k); 119 120 120 for (int i = 0; i < length; ++i) { 121 yield return range.Select(x => elements[x]); 122 if (i == length-1) break; 123 var m = k - 1; 124 var max = n - 1; 125 while (range[m] == max) { --m; --max; } 126 range[m]++; 127 for (int j = m + 1; j < k; ++j) { 128 range[j] = range[j-1] + 1; 129 } 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; 130 132 } 131 133 } … … 138 140 /// using the recursion C(N+1, K+1) = (N+1 / K+1) * C(N, K). 139 141 /// <remarks>http://blog.plover.com/math/choose.html</remarks> 142 /// <remark>https://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula</remark> 140 143 /// <param name="n">The number of elements</param> 141 144 /// <param name="k">The size of the group</param> 142 145 /// <returns>The binomial coefficient C(N, K)</returns> 143 146 /// </summary> 144 public static long BinomialCoefficient(long n, long k) 147 public static long BinomialCoefficient(long n, long k) { 145 148 if (k > n) return 0; 146 149 if (k == n) return 1; … … 148 151 k = n - k; 149 152 long r = 1; 150 for (long d = 1; d <= k; d++) 153 for (long d = 1; d <= k; d++) { 151 154 r *= n--; 152 155 r /= d;
Note: See TracChangeset
for help on using the changeset viewer.