The festival ledger

A festival programmer keeps a ledger of every possible running order and screens line k on night k. The ledger is far too long to print, and the answer does not need it.

The problem

A short-film festival has n reels, numbered 1 to n, and shows all of them every night in some order. The ledger lists every running order once, sorted the way a dictionary sorts words: compare two orders reel by reel from the front, and the smaller reel at the first difference wins.

On night k the festival screens line k, counting from 1. Given n and k, report that running order.

Input. n — the number of reels. k — the line number, from 1 to n!.

Output. A list of n reel numbers: the running order on line k.

Example.

n = 3, k = 3   ->  [2, 1, 3]

The ledger for three reels reads 123, 132, 213, 231, 312, 321. Line 3 is 213.

A second example, large enough that counting lines by hand is the wrong move:

n = 4, k = 9   ->  [2, 3, 1, 4]

Six orders begin with reel 1, so they take lines 1 to 6. Line 9 is the third order beginning with reel 2: 2134, 2143, 2314.

Constraints.

• 1 <= n <= 9
• 1 <= k <= n!

Hints

Approach

Brute force

Walk the choice tree in order, generating running orders and counting to k. At n = 9 that builds and discards up to 362,879 orders of nine reels — about 3.3 million appends for one answer — and grows factorially with n.

The insight

Every subtree in the choice tree has a size you can compute instead of walking: fixing the first reel leaves exactly (n - 1)! orders, so a block can be skipped whole.

Dictionary order is what makes this legal: orders sharing a first reel sit in one contiguous block, and the blocks run in increasing order of that reel, so they are equal in size and in a known sequence. Dividing the 0-based rank by the block size names the block; the remainder is the rank inside it, the same question with one fewer reel.

That turns backtracking into arithmetic — instead of descending into a subtree to count its leaves, compute the count and step over it. n divisions replace k visits.

Algorithm

1. Keep remaining = [1, 2, ..., n] in increasing order, and rank = k - 1.
2. For slots_left running from n - 1 down to 0:
   • block = slots_left!, the number of lines that share any one next reel.
   • index, rank = divmod(rank, block).
   • Remove remaining[index] and append it to the answer; the list stays increasing, so the next index still names a block correctly.
3. After n steps the answer holds the running order.

Complexity

Time O(n²) — n steps, each removing from a list of at most n reels. At n = 9 that is under 100 operations, against 362,880 for the enumeration. Space O(n) for the remaining reels and the answer.

Solution

"""The festival ledger — skip whole subtrees using factorial block sizes."""

from math import factorial


def solve(n, k):
    remaining = list(range(1, n + 1))
    order = []
    rank = k - 1              # invariant: rank is the 0-based position of the
                              # wanted line among the lines that still start
                              # with everything already appended to `order`
    for slots_left in range(n - 1, -1, -1):
        block = factorial(slots_left)     # lines sharing any one next reel
        index, rank = divmod(rank, block)
        order.append(remaining.pop(index))
    return order

TESTS = [
    ((3, 3), [2, 1, 3]),
    ((4, 9), [2, 3, 1, 4]),
    ((1, 1), [1]),
    ((4, 1), [1, 2, 3, 4]),
    ((4, 24), [4, 3, 2, 1]),
    ((9, 362880), [9, 8, 7, 6, 5, 4, 3, 2, 1]),
]

Pitfalls

• Dividing the 1-based k instead of k - 1. Every block boundary shifts by a line: n = 3, k = 3 returns [2, 3, 1], which is line 4 of the ledger.
• Reading remaining[index] without removing it. The list never shrinks, so reels repeat and later indices point at the wrong block: n = 4, k = 9 returns [2, 2, 1, 1], which is not a running order at all.
• Removing by swapping in the last element. It is O(1) instead of O(n), but it leaves remaining out of order, and the index only names the right block while the list is increasing: n = 4, k = 9 becomes [2, 4, 1, 3].
• Using the size of the block you are in rather than the blocks you are choosing between. Dividing by (slots_left + 1)! makes the first index 0 every time; n = 4, k = 9 returns [1, 3, 4, 2].

Variants

• Whole-turn gearing — the same permutation tree, but every branch has to be entered, because feasibility rather than size decides what to skip.
• Pruning — the lesson on cutting subtrees; here the entire answer is one long sequence of cuts.