A combination number is the zero-based position of a fixed-size combination in the ordering used here. For k distinct numbers chosen from 0 through n−1, the numbers run from 0 to (n choose k)−1. The ordering groups combinations by their largest element: those not containing n−1 come before those containing it. This makes a combination number useful for retrieving one combination without generating every earlier one. section 6.3.2 section 6.3.2
To retrieve number p, split the combinations at (n−1 choose k). Below that boundary, recurse among combinations drawn from 0 through n−2. At or above it, subtract the boundary, retrieve a size-(k−1) combination from that smaller range, and append n−1. The empty combination ends the recursion. For a valid index, this gives combination number 8 of size 4 from 0 through 5 as 1235. section 6.3.2 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 C# implementation uses the count of combinations without n−1 as the branch boundary. Its recursive calls either retain p or subtract that boundary before appending n−1. section 6.3.2
Rank 0245
For a combination written in increasing order as 0, 2, 4, 5, add one binomial term for each position: (0 choose 1) + (2 choose 2) + (4 choose 3) + (5 choose 4) = 0 + 1 + 4 + 5 = 10. Thus 0245 has combination number 10 in this ordering. section 6.3.3 section 6.3.3
In general, if the increasing elements are a₀ through aₖ₋₁, their combination number is the sum of (aᵢ choose i+1). This direct calculation examines the combination’s elements rather than recursively reducing n. It also shows why the rank does not depend on a specified n, provided the range contains every element. Binomial counts can be large, so the C# implementations use BigInteger; when calculating a binomial coefficient with integer division, multiply before dividing to avoid premature rounding. section 6.3.3 section 6.3.2
Listing 6.21 Generating combination numbers directly
static class Extensions
{
public static BigInteger GetCombNumber(this IList<int> comb)
{
BigInteger result = 0;
int k = comb.Count;
for (int i = 0; i < k; i += 1)
result += comb[i].Choose(i + 1);
return result;
}
}
The direct C# ranking method accumulates one Choose term per element, using its one-based position as the term’s lower argument. section 6.3.3
