Ranking (source code)
= Ranking
{title2=$\operatorname{rank}$}
Ranking assigns each object in a finite ordered combinatorial family its zero-based position, giving a <bijection> with consecutive <nonnegative integers>. Its inverse is <unranking>. For an $r$-element <subset> $\{a_1<\cdots<a_r\}$ of $\{0,\ldots,n-1\}$, its rank in <colexicographic order> is
$$
\operatorname{rank}\{a_1,\ldots,a_r\}=\sum_{j=1}^r\binom{a_j}{j}.
$$
This is the <combinatorial number system>, with $\binom aj=0$ when $a<j$. All ranks from $0$ to $\binom nr-1$ occur exactly once.
For two-element <subsets>, <colexicographic order> begins $\{0,1\},\{0,2\},\{1,2\},\{0,3\},\{1,3\},\{2,3\}$. Their ranks are $0,1,2,3,4,5$. In particular, $\{1,3\}$ has rank $\binom11+\binom32=4$. The binomial sum counts all preceding subsets by the largest element where they differ. Ranking turns structured objects into compact array indices and permits uniform sampling by drawing a uniform rank and applying <unranking>.
Back to article page
