1161. Orderings Where Nothing Stays Put
Sort the n given distinct values. Call the result a, so a[0] is the
smallest and position i is the HOME of a[i].
Print every ordering of the values in which no value is at its own home.
3
1 2 3 -> 2 3 1
3 1 2
1 2 3 is out because all three are home. 1 3 2 is out because 1 is home,
even though the other two moved. The rule is about every position, not most of
them.
## What most people try first
Generate all n! orderings and throw away the ones with a fixed value. That is
correct and it keeps a shrinking share of what it builds: the fraction of
orderings with nothing in place tends to 1/e, about 0.368, so roughly two in
three leaves are built and discarded. At n = 8 that is 40320 built and 14833
kept.
The waste is avoidable because the rule is checkable the moment a value is
placed. If a[i] goes to position i, that ordering is already dead and so is
everything below it in the search, which is (n - 1 - i)! leaves at depth i.
## The method
Fill positions left to right. At position pos, try every unused value except
the one whose home is pos:
go(pos):
if pos == n: record cur; return
for i in 0 .. n-1:
if used[i] or i == pos: continue
used[i] = true; cur.push(a[i])
go(pos + 1)
cur.pop(); used[i] = false
The whole constraint is the single test i == pos, which works because the
values were sorted, so the index of a value in a IS its home.
## Why it is correct
The search fills each position exactly once and each value is used exactly once, so every leaf is an ordering, and every ordering with no value at home is reachable because the only branch ever refused is one that would put a value at its home. Conversely no leaf can have a value at home, because that branch is refused at the moment of the push. So the leaves are exactly the answers.
## The output convention, shared by every problem in this block
Values inside one ordering are separated by single spaces, and orderings are
printed one per line. Two orderings are compared position by position
NUMERICALLY, and when one is a prefix of the other the shorter comes first. If
there are no orderings at all, print none.
## The boundary that is easy to get wrong
n = 1 has NO answer. The single value has nowhere else to go, so the output is
none, not the value itself and not a blank line. n = 2 has exactly one
answer, the swap.
## Cost
Proportional to the number of answers times O(n) to print, with the pruning
cutting the dead subtrees as soon as they appear. The answer count is the
derangement number, 14833 at n = 8.
Constraints - `1 ≤ n ≤ 8` - `-1000 ≤ a[i] ≤ 1000` - All values are distinct.
Input
The first line contains an integer n.
The second line contains n space-separated distinct integers.
Output
Print every ordering in which no value sits at its own home on its own line, values separated by single spaces, the lines ordered as described. Print none if there are no such orderings.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.