unranking

Unranking is the process of constructing a combinatorial object from its rank within a fixed enumeration of objects, and is the inverse operation of ranking. It is used to generate objects in a specified order, to sample objects randomly by selecting a rank and unranking it, and to enumerate large or complex search spaces without duplications.

In the case of permutations of n elements, ranks range from 0 to n! − 1. Unranking decodes a rank into a permutation, typically via the factorial number system (Lehmer code). One computes digits that represent the position of each next element among the remaining unused elements, and then selects elements accordingly to build the permutation.

For combinations, unranking maps a rank r in 0 ≤ r < C(n, k) to the r-th k-subset in lexicographic order. This often uses the combinatorial number system, where binomial coefficients guide decisions about whether to include certain elements as the construction proceeds, ensuring the resulting subset aligns with the desired rank.

Unranking also applies to other object classes such as trees and graphs, frequently requiring recursive decompositions or encoding schemes that preserve a fixed enumeration. Different orderings, such as lexicographic or colexicographic, determine the exact mapping between ranks and objects, and specialized algorithms may optimize for particular classes or representations.

Applications include systematic generation of all objects in a given class, random sampling by selecting a random rank, and exhaustive search methods in algorithm design and testing. The efficiency of unranking algorithms typically scales with the size of the object, often running in time linear in the object’s size, with specific bounds depending on the encoding used.