This content details the mathematical concept of the Combinatorial Number System, also referred to as Combinadics, and its application in efficiently generating the $m$-th lexicographical element of an $(n, k)$ combination (the "unranking" operation). The combinadic is introduced as an alternative integer representation based on a variable base corresponding to binomial coefficients $\binom{n}{k}$. This direct method bypasses the performance limitations of iterative approaches when dealing with combinations where $n$ and $k$ are large (e.g., over $22$ quadrillion possible elements for $C(200, 10)$). The algorithm involves calculating the "dual" index of $m$, finding its combinadic representation, and then converting the combinadic digits to the final combination elements. Accompanying material provides C# code demonstrating the algorithm using large integers (BigInteger) and a high-performance Python implementation leveraging jax for GPU-accelerated, vectorized calculation.
Generating the $m$-th Lexicographical Element of a Combination using Combinadics
Core Concept (Combinadics): The Combinatorial Number System (or "Combinadic") is a unique way to represent an integer $N$ as a sum of binomial coefficients: $N = \binom{c_k}{k} + \binom{c_{k-1}}{k-1} + \cdots + \binom{c_1}{1}$, where $c_k > c_{k-1} > \dots > c_1 \geq 0$.
Purpose: The primary goal is to directly generate the $m$-th lexicographical element of an $(n, k)$ combination (known as "unranking"). This avoids inefficient iterative methods, which become infeasible when the total number of combinations, $\binom{n}{k}$, is astronomically large.
Lexicographical Ordering: Combinations are ordered based on the decreasing sequence of their elements. For example, in $C(5, 3)$, ${0, 1, 2}$ precedes ${0, 1, 3}$.
Finding the Combinadic (Greedy Algorithm): To find the combinadic representation of a number $m$, one iteratively finds the largest coefficient $c_i$ such that $\binom{c_i}{i}$ is less than or equal to the remaining value of $m$, repeating the process for the remainder with decreasing $i$.
Conversion Algorithm (Using Duals): To find the combination element for index $m$ (0-based) given parameters $n$ and $k$:
Determine the maximum index: $MaxIndex = \binom{n}{k} - 1$.
Calculate the dual index: $x = MaxIndex - m$.
Find the combinadic representation $(c_k, c_{k-1}, \dots, c_1)$ of $x$.
The final combination elements are determined by subtracting each digit from $n-1$: $Element_i = (n-1) - c_i$.
Practical Implementation: Due to the potential size of $\binom{n}{k}$ for moderate $n$ and $k$, software implementations must use large number arithmetic (e.g., C# uses BigInteger) or specialized array processing.
High-Performance Computing: A Python implementation utilizing the jax library demonstrates how the combinadic calculation can be vectorized (jax.vmap) and compiled for GPU execution (cuda_calculateMth), achieving fast calculation of combinations in parallel.
Historical Context: The method is a modern application of the combinatorial number system, mathematically studied by Pascal (1887) and Lehmer (1964), often referred to as the Macaulay representation. The term "Combinadic" was coined by James McCaffrey.