Unranking

Unranking is the inverse of ranking: given an index $k$ into an ordered family of objects, construct the $k$-th object directly, without generating the $k - 1$ before it. Project Euler asks for this often. "The millionth permutation", "the $10^{16}$-th number with property $X$": $k$ is far too large to count up to, but the objects are built one symbol at a time, and you can count how many objects begin with a given prefix. The four solved problems below use the same construction loop. They differ in the counting function behind it, from a closed form ($n!$) through a sum of multinomial coefficients to a digit DP table.

The idea — count the subtree, skip it or enter it

Arrange the objects in lexicographic order as the leaves of a tree: the root's children are the possible first symbols, their children the second symbols, and so on. To find leaf $k$ (1-based):

for each position, left to right:
    for each candidate symbol c, in order:
        w = number of valid completions of prefix + c
        if k <= w: append c; break      # the target is in this subtree
        k -= w                          # skip the whole subtree

The loop does $O(\text{length} \times \text{alphabet})$ calls to the count function. Everything interesting is in how $w$ is computed:

  • If every prefix of the same length has the same number of completions, $w$ is a closed form and the loop becomes divmod. For permutations, that is the factorial number system.
  • If the count depends on a summary of the prefix (a digit sum, a residue, a parity mask), precompute a table count[remaining length][summary] by DP, then look $w$ up in it.

The same table answers "how long is the $k$-th object?". Subtract whole lengths' counts first, then unrank within the right length.

Four problems, four counting functions

24, lexicographic permutations: a closed form. All $(n-1)!$ completions of a one-digit prefix are valid, so the leading digit is the quotient of $k - 1$ by $(n-1)!$, and the remainder is the rank within that block. The public solution writes it recursively:

current, remaining = divmod(permutation_number - 1, math.factorial(len(digits) - 1))
result: str = digits[current] + recursive_solution(
    digits=digits[:current] + digits[current + 1:], permutation_number=remaining + 1
)

Ten steps, against the $10^6$ that itertools.permutations would have to step through.

698, 123-numbers: a sum of multinomials over digit counts. A 123-number uses only the digits 1, 2, 3, and each digit's count is either 0 or itself a 123-number; we need the $n$-th one for $n$ around $10^{17}$. The rule never looks at the order of the digits, only at the count triple $(c_1, c_2, c_3)$, so the prefix summary is the vector of digits used so far, $(u_1, u_2, u_3)$, and there is no table at all. The number of completions is a direct sum over the admissible final triples $c_i \ge u_i$ with $c_1 + c_2 + c_3 = L$: $$w = \sum \binom{L - |\text{prefix}|}{c_1 - u_1,\; c_2 - u_2,\; c_3 - u_3},$$ a multinomial coefficient for each triple. Admissible counts are few (only a dozen below 111), so each query is a few hundred terms. Two details are worth stealing. The self-reference resolves itself during the length phase: whether $L$ is admissible depends only on smaller counts, so the solution appends $L$ to the admissible list just before it counts the length-$L$ block. And because the answer is wanted modulo a constant, each chosen digit is folded into a running residue, so the full number is never held.

845, prime digit sum: a DP over digit sums. We need the $n$-th positive integer whose digit sum is prime, with $n$ up to $10^{16}$. Whether a completion is valid depends only on the prefix's digit sum, so the solution builds counts[length][s], the number of length-$\ell$ digit strings (leading zeros allowed) with digit sum $s$. The number of completions of a prefix with sum $p$ is then $\sum_s \text{counts}[\ell][s] \cdot [\,p + s \text{ prime}\,]$. The table grows until it covers $n$ valid numbers. Then the loop fixes digits from most significant to least significant. Leading zeros come out naturally: a number with fewer digits is a string with leading zeros, and the all-zero string has sum 0, which is never prime, so it is never counted.

974, very odd numbers: a DP over a richer state. Here the valid objects have only odd digits, are divisible by 105, and use each odd digit an odd number of times. The state after a prefix is (value mod 7, digit sum mod 3, a 5-bit mask of digit-count parities), and the last digit is forced to be 5 for divisibility by 5. The solution tabulates completions over $7 \times 3 \times 32$ states for each remaining length, skips whole lengths (only odd lengths $\ge 5$ are possible) until the rank falls inside one, and then runs the same skip-or-enter loop. The richer state changes only the DP, not the construction.

Python and C

  • 24: identical recursion. Python's string slicing digits[:current] + digits[current + 1:] becomes a malloced copy with one character skipped, and each level allocates a new result string. C's long long factorial is ample for ten digits. It would overflow past $20!$, where Python keeps going.
  • 698: Python's exact integers make $L!/(c_1!\,c_2!\,c_3!)$ safe. In C, $L!$ overflows even unsigned __int128, so the port writes each multinomial as a product of two binomials, $\binom{r}{x}\binom{r-x}{y}$, read from a Pascal's-triangle table; no intermediate value exceeds $3^r$, the total number of length-$r$ strings.
  • 845: Python grows counts as a list of lists only as long as needed. C allocates a static long long counts[MAX_LEN + 1][MAX_SUM + 1] with fixed generous bounds and memsets it for each call. For $n = 10^{16}$ the table stops at about 18 digits, so every count and every prefix total is below $10^{18}$ and fits a signed 64-bit integer.
  • 974: the DP counts grow like $5^{\ell}$ and pass $2^{64}$ for long enough numbers, so C stores them as unsigned __int128 in a flat array with a hand-written index function (cget), and formats the 128-bit result itself. Python's dict keyed by 4-tuples and its unbounded int need neither. The Python also re-runs build_counts from scratch each time it grows max_len, a simplicity-over-speed choice that the tiny state space makes affordable.

How to reason about it

  • Is there an order and a way to count by prefix? Then the $k$-th object can be built in $O(\text{length} \times \text{alphabet})$ count queries, however large $k$ is.
  • Find the smallest prefix summary that determines validity. That summary is the DP state: nothing for permutations, the used-digit counts for 698, the digit sum for 845, (mod 7, mod 3, parity mask) for 974. When validity depends only on the multiset of symbols, as in 698, the count of completions is a sum of multinomials and needs no DP.
  • Use 0-based ranks inside the loop. divmod(k - 1, …) avoids the off-by-one that 1-based ranks invite. Convert back only at the boundary.
  • Settle the length first. Subtract the counts of whole shorter lengths, or let leading zeros stand in for shorter numbers as 845 does. Do not mix the two.
  • Mind the width of the counts, not just of the answer. The intermediate counts can exceed the answer by orders of magnitude (974).

Problems5 / 5

  • ● 0024 — Lexicographic Permutations
  • ● 0698 — 123 Numbers
  • ● 0845 — Prime Digit Sum
  • ● 0912 — Where are the Odds?
  • ● 0974 — Very Odd Numbers