Changeset 13899


Ignore:
Timestamp:
06/16/16 15:33:47 (3 years ago)
Author:
mkommend
Message:

#2602: Code cleanup in EnumerableExtensions for calculating combinations of length k.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Common/3.3/EnumerableExtensions.cs

    r13802 r13899  
    108108      if (k > elements.Count)
    109109        throw new ArgumentException();
     110
    110111      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      }
    117116
    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);
    119120
    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;
    130132        }
    131133      }
     
    138140    /// using the  recursion C(N+1, K+1) = (N+1 / K+1) * C(N, K).
    139141    /// <remarks>http://blog.plover.com/math/choose.html</remarks>
     142    /// <remark>https://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula</remark>
    140143    /// <param name="n">The number of elements</param>
    141144    /// <param name="k">The size of the group</param>
    142145    /// <returns>The binomial coefficient C(N, K)</returns>
    143146    /// </summary>
    144     public static long BinomialCoefficient(long n, long k)  {
     147    public static long BinomialCoefficient(long n, long k) {
    145148      if (k > n) return 0;
    146149      if (k == n) return 1;
     
    148151        k = n - k;
    149152      long r = 1;
    150       for (long d = 1; d <= k; d++)   {
     153      for (long d = 1; d <= k; d++) {
    151154        r *= n--;
    152155        r /= d;
Note: See TracChangeset for help on using the changeset viewer.