1162. The kth Ordering Without Listing Them All

Given n distinct integers and a number k, print the kth ordering of all of them in lexicographic order, counting from 1. If fewer than k orderings exist, print none.

3 1 1 2 3 -> 1 2 3 the orderings in order are 3 4 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1 1 2 3 -> 2 3 1

## What most people try first

Generate the orderings in lexicographic order and stop at the kth, which is what problem 1149 does for bracket strings. It works and it is unusable here: n reaches 18, so there are 18! orderings, which is 6402373705728000. Walking to the kth at a billion steps a second would take two and a half months, and the answer is eighteen numbers long.

A second attempt, which looks much more promising, is to call a next-ordering routine k - 1 times. It is a real algorithm and it is still k steps. The problem is not how expensive one step is, it is that k steps is the wrong order of magnitude.

## The counting that replaces the walk

Fix the first value. Once chosen, the rest can be arranged in (n-1)! ways, and all of those orderings are adjacent in lexicographic order. So the orderings split into n blocks of (n-1)!, one block per choice of first value, and the blocks are in increasing order of that value.

That is enough to find the first value by division. Then repeat inside the block.

k = k - 1 # count from 0 rem = sorted values for pos in 0 .. n-1: f = (n - 1 - pos)! # size of each block at this depth idx = k / f # integer division k = k - idx * f output rem[idx]; remove rem[idx]

This is the factorial number system: the digits idx at successive depths are exactly the digits of k in bases n, n-1, ..., 1.

## Why it is correct

Claim: after the step at depth pos, the remaining k is the 0-based index of the wanted ordering among the orderings of the values still in rem, listed lexicographically.

At depth 0 that is the definition. Suppose it holds at depth pos, where rem has n - pos values and so (n - pos)! orderings, and 0 <= k < (n - pos)!. Those orderings are grouped by first value into n - pos consecutive blocks of f = (n - pos - 1)!, in increasing order of the value, because comparing two orderings with different first values is decided by that first value alone. The block containing index k is number k / f, which is idx, and the index inside it is k - idx * f. Since rem is kept sorted, rem[idx] is the value of that block, and removing it leaves the values of the inner problem. So the claim holds at pos + 1, and 0 <= k < f there.

No undo appears anywhere. Each digit is decided once, because the arithmetic proves the answer is inside the chosen block before the step is taken.

## Overflow, and it bites immediately

18! is 6402373705728000. A signed 32 bit integer stops at 2147483647, and 13! already passes it, so k, the factorials, and the product idx * f all need 64 bits. Three concrete failures:

• holding k in 32 bits wraps any k above two billion into a negative
• number, after which k / f is negative and the program indexes before the
• start of the list
• computing the factorial table in 32 bits silently gives the wrong block size
• from 13! on, so the division picks the wrong value and the output is a valid
• looking ordering that is not the kth
• 18! is below 2^53, so a language with only double precision numbers can
• hold it exactly, but the quotient must be taken with an exact integer
• division; and the safe move there is an arbitrary precision integer type

## Cost

O(n^2) at worst, from removing a value out of the middle of the list n times, which is 324 operations at n = 18. The number of orderings never appears in the running time.

Constraints - `1 ≤ n ≤ 18` - `1 ≤ k ≤ 6402373705728000` - `-1000 ≤ a[i] ≤ 1000` - All values are distinct.