Index: stable/HeuristicLab.Common/3.3/EnumerableExtensions.cs
===================================================================
--- stable/HeuristicLab.Common/3.3/EnumerableExtensions.cs (revision 13952)
+++ stable/HeuristicLab.Common/3.3/EnumerableExtensions.cs (revision 13953)
@@ -1,5 +1,5 @@
#region License Information
/* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
*
* This file is part of HeuristicLab.
@@ -98,4 +98,63 @@
return sequences.Where(s => s.Any()).Aggregate(result, (current, s) => (from seq in current from item in s select seq.Concat(new[] { item })));
}
+
+ ///
+ /// Compute all k-combinations of elements from the provided collection.
+ /// The collection of elements
+ /// The combination group size
+ /// An enumerable sequence of all the possible k-combinations of elements
+ ///
+ public static IEnumerable> Combinations(this IList elements, int k) {
+ if (k > elements.Count)
+ throw new ArgumentException();
+
+ if (k == 1) {
+ foreach (var element in elements)
+ yield return new[] { element };
+ yield break;
+ }
+
+ int n = elements.Count;
+ var range = Enumerable.Range(0, k).ToArray();
+ var length = BinomialCoefficient(n, k);
+
+ for (int i = 0; i < length; ++i) {
+ yield return range.Select(x => elements[x]);
+
+ if (i == length - 1) break;
+ var m = k - 1;
+ var max = n - 1;
+
+ while (range[m] == max) { --m; --max; }
+ range[m]++;
+ for (int j = m + 1; j < k; ++j) {
+ range[j] = range[j - 1] + 1;
+ }
+ }
+ }
+
+ ///
+ /// This function gets the total number of unique combinations based upon N and K,
+ /// where N is the total number of items and K is the size of the group.
+ /// It calculates the total number of unique combinations C(N, K) = N! / ( K! (N - K)! )
+ /// using the recursion C(N+1, K+1) = (N+1 / K+1) * C(N, K).
+ /// http://blog.plover.com/math/choose.html
+ /// https://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula
+ /// The number of elements
+ /// The size of the group
+ /// The binomial coefficient C(N, K)
+ ///
+ public static long BinomialCoefficient(long n, long k) {
+ if (k > n) return 0;
+ if (k == n) return 1;
+ if (k > n - k)
+ k = n - k;
+ long r = 1;
+ for (long d = 1; d <= k; d++) {
+ r *= n--;
+ r /= d;
+ }
+ return r;
+ }
}
}