Changeset 13802
 Timestamp:
 04/27/16 12:25:39 (5 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/sources/HeuristicLab.Common/3.3/EnumerableExtensions.cs
r12012 r13802 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 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; 117 118 var length = BinomialCoefficient(n, k); 119 120 for (int i = 0; i < length; ++i) { 121 yield return range.Select(x => elements[x]); 122 if (i == length1) 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[j1] + 1; 129 } 130 } 131 } 132 } 133 134 /// <summary> 135 /// This function gets the total number of unique combinations based upon N and K, 136 /// where N is the total number of items and K is the size of the group. 137 /// It calculates the total number of unique combinations C(N, K) = N! / ( K! (N  K)! ) 138 /// using the recursion C(N+1, K+1) = (N+1 / K+1) * C(N, K). 139 /// <remarks>http://blog.plover.com/math/choose.html</remarks> 140 /// <param name="n">The number of elements</param> 141 /// <param name="k">The size of the group</param> 142 /// <returns>The binomial coefficient C(N, K)</returns> 143 /// </summary> 144 public static long BinomialCoefficient(long n, long k) { 145 if (k > n) return 0; 146 if (k == n) return 1; 147 if (k > n  k) 148 k = n  k; 149 long r = 1; 150 for (long d = 1; d <= k; d++) { 151 r *= n; 152 r /= d; 153 } 154 return r; 155 } 100 156 } 101 157 }
Note: See TracChangeset
for help on using the changeset viewer.