Changeset 13953


Ignore:
Timestamp:
06/29/16 14:15:06 (3 years ago)
Author:
mkommend
Message:

#2602: Merged r13802, r13899 into stable.

Location:
stable
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • stable

  • stable/HeuristicLab.Common/3.3/EnumerableExtensions.cs

    r12009 r13953  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
     
    9898      return sequences.Where(s => s.Any()).Aggregate(result, (current, s) => (from seq in current from item in s select seq.Concat(new[] { item })));
    9999    }
     100
     101    /// <summary>
     102    /// Compute all k-combinations 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 k-combinations 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    }
    100159  }
    101160}
Note: See TracChangeset for help on using the changeset viewer.