1233. Every Ordering, One Swap at a Time

Print the first k orderings of 1 to n in PLAIN CHANGES order, or all of them if there are fewer than k. Plain changes order is defined like this, with no reference to any program:

> The sequence for n = 1 is the single ordering 1. > > The sequence for n is built from the sequence for n - 1 by replacing each > of its orderings, in turn, by n orderings: insert the value n into that > ordering at every one of the n possible positions. For the 1st, 3rd, 5th, > ... ordering of the shorter sequence, insert from the rightmost position > leftwards. For the 2nd, 4th, 6th, ... insert from the leftmost position > rightwards.

n = 3, the whole sequence 1 2 3 from 1 2, inserting 3 right to left 1 3 2 3 1 2 3 2 1 from 2 1, inserting 3 left to right 2 3 1 2 1 3

Consecutive orderings differ by swapping two NEIGHBOURS. That is a theorem about the rule above, not part of the specification.

## 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.

## What most people try first

Print the orderings in lexicographic order, which is what next permutation gives and what #1147 uses. It is a different order and it does not have the one-swap property: 1 3 2 to 2 1 3 moves everything.

The second instinct is to follow the recursive rule literally, building the whole sequence for n - 1 and then expanding it. That is correct and it holds (n-1)! orderings in memory to produce n!, so it uses the whole output as working space. For n = 8 that is 40320 orderings held to print at most 400.

## Generating directly, by largest mobile value

Give every value a direction, initially leftwards. Then:

repeat: find the largest value that can move one step in its own direction into a position holding a SMALLER value if there is none: stop swap it with that neighbour reverse the direction of every value LARGER than the one just moved

Each step produces the next ordering, so the first k can be printed without holding any of them. That is what makes the k in the input worth having: the recursive rule needs the whole sequence, this needs one ordering.

## Why the two agree

The recursive rule inserts n into a shorter ordering at every position, moving one position per step, alternating direction between successive shorter orderings. In the mobile-value algorithm, n is the largest value, so while n can move it is always the one chosen, and it moves one step per iteration in its own direction, sweeping across the ordering. When n reaches an end it can no longer move, the algorithm picks the largest value below n that can, and reverses the direction of n, which is exactly the alternation in the recursive rule applied at the next level down. By induction on n the two sequences agree.

That argument is the content of this problem. The two constructions look nothing like each other, the equality is not obvious, and the verification for this problem runs both and compares them position by position on every size.

## The settled boundaries

n = 1 has one ordering. k larger than n! prints all n! of them, which is tested at n = 2 with k = 5. k = 1 prints only the first ordering, which is 1 2 3 ... n.

## Cost

O(n) per ordering with the mobile-value algorithm, so O(k * n) in all, and O(n) memory. The recursive construction is O(n!) memory whatever k is.

Constraints - `1 ≤ n ≤ 8` - `1 ≤ k ≤ 400`