1239. The Next Few Orderings After This One

An ordering of 1 to n is given. Print the next k orderings after it in LEXICOGRAPHIC order, or as many as exist if fewer than k come after it. Print none if the given ordering is the last one.

n = 4, k = 3, starting from 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2

## Why the order has to be pinned, and pinned without naming a program

A set of answers has no order. If a statement says only "print them all", two correct programs produce two different outputs and no automated check can tell a correct program from a broken one. So the order is part of the specification.

The second trap is pinning it as "the order your search finds them in". That names a program rather than a rule, and it is not a specification: a search that tries its options in a different sequence finds the same answers in a different order and is equally entitled to call itself correct. The rule below mentions no search.

The rule here is ordinary lexicographic order on the value sequences, which is unambiguous.

## What most people try first

List all n! orderings in order, find the given one, and take the k after it. That is correct and it needs every ordering, at n = 8 all 40320 of them, to answer a question about at most 400. It also needs them sorted or generated in order, which is the same work again.

The question only asks for a step, so compute the step.

## The step

Given an ordering, the next one in lexicographic order is found like this:

find the largest i with a[i] < a[i+1] the last ASCENT if there is none: this is the last ordering, answer none find the largest j > i with a[j] > a[i] swap a[i] and a[j] reverse everything after position i

## Why that is the next one and not merely a later one

Everything after position i is non-increasing, by the choice of i as the last ascent, so the tail is already at its largest arrangement and no ordering beginning with the same first i+1 values comes after the given one. The next ordering must therefore raise position i.

It must raise it as little as possible, so a[i] is replaced by the smallest value to its right that is larger than it. Because the tail is non-increasing, scanning from the right end and stopping at the first value larger than a[i] finds exactly that smallest one.

After the swap the tail is still non-increasing, which is the step people get wrong: the swap puts a[i] where a[j] was, and a[i] is smaller than everything before j in the tail and at least as large as everything after it, so the ordering of the tail is preserved. Reversing it makes it non-decreasing, which is its smallest arrangement. So the result is the smallest ordering above the given one.

Each of those three claims is a place to get it wrong. Taking the FIRST ascent instead of the last skips orderings. Taking the largest value larger than a[i] instead of the smallest skips orderings. SORTING the tail instead of reversing it is correct but turns an O(n) step into O(n log n) for no reason, and hides the fact that the tail was already in order.

## The settled boundaries

The fully reversed ordering n n-1 ... 1 has no successor, so the answer is none; that is tested. k larger than the number of orderings after the given one prints all of them and stops. n = 1 has exactly one ordering, so the answer is always none whatever k is.

## Cost

O(n) per step, so O(k * n) in all, and O(n) memory, against O(n! * n) for listing everything.

Constraints - `1 ≤ n ≤ 8` - `0 ≤ k ≤ 200` - the second line is a rearrangement of `1` to `n`