A combination chooses k items from a sequence of n items without changing their order. For ABCDE with k = 3, ABC, ABE, and CDE qualify; a reordering does not. Where permutations help test what happens when actions run in a different order, combinations help test what happens when some actions are skipped. section 6.3
Choose positions, then apply them
Generate combinations of the indices 0 through n−1, then use those indices with any list. For ["ham", "jam", "spam", "lamb"], the index combination [1, 2] selects ["jam", "spam"]. This separates the selection algorithm from the type of item being selected. section 6.3
Two ways to enumerate combinations expose different useful structures:
- For a mutable, right-to-left lexicographic enumeration, start at 0, 1, …, k−1. To advance, increment the rightmost position that can increase while leaving the indices strictly increasing, then reset every position to its left to its smallest possible value. With n = 6 and k = 4, 1245 advances to 0345. Stop when no position can increase. section 6.3.1
- For a recursive enumeration, split combinations by whether they contain n−1. First yield the k-item combinations from 0 through n−2; then append n−1 to each (k−1)-item combination from that range. An impossible choice yields nothing, while choosing zero items yields one empty combination. section 6.3.1
Listing 6.17 An elegant recursive method for generating combinations
static IEnumerable<IDeque<int>> Combinations2(int n, int k)
{
if (k > n || k < 0)
yield break; #1
if (k == 0)
{
yield return Deque<int>.Empty; #2
yield break;
}
foreach (var r in Combinations2(n - 1, k)) #3
yield return r;
foreach (var r in Combinations2(n - 1, k - 1)) #4
yield return r.PushRight(n-1);
}
The C# iterator makes the include-or-exclude split concrete; its deque result lets the recursive branch append an index without mutating an earlier result. section 6.3.1
The number of results is n C k, pronounced “n choose k.” There is one empty combination, none when k > n, and n C k = n C (n−k): choosing items corresponds to identifying those left out. The recursive split gives n C k = (n−1) C k + (n−1) C (k−1). Equivalently, n C k = n(n−1)…(n−k+1)/k!: counting selection orders overcounts each combination by the k! orders of its chosen items. section 6.3.2
Listing 6.18 Implementing the Choose operator
static class Extensions
{
public static BigInteger Choose(this int n, int k)
{
if (k > n)
return 0; #1
if (k > n / 2) #2
k = n - k;
BigInteger result = 1; #3
for (int i = 1; i <= k; i += 1)
result = result * (n - k + i) / i; #4
return result;
}
}
The Choose implementation uses symmetry to shorten its loop and BigInteger for the count, multiplying and dividing incrementally rather than forming the entire numerator first. section 6.3.2
Counting also lets you retrieve a combination directly by its position p, without enumerating every earlier result. The first (n−1) C k results omit n−1. If p lies beyond that boundary, subtract it, find the corresponding (k−1)-item combination, and append n−1. section 6.3.2
Listing 6.19 Recursively generating combinations from combination numbers
static IDeque<int> GetCombination(BigInteger p, int n, int k)
{
if (k > n || k == 0)
return Deque<int>.Empty;
var boundary = (n - 1).Choose(k);
return p < boundary ?
GetCombination(p, n - 1, k) :
GetCombination(p - boundary, n - 1, k - 1).PushRight(n - 1);
}
The recursive GetCombination method turns the counting boundary into a branch decision for a requested combination index. section 6.3.2
