1164. Orderings That Zigzag
Given n distinct integers, print every ordering that zigzags: the second
value is greater than the first, the third is less than the second, the fourth
is greater than the third, and so on alternately.
4
1 2 3 4 -> 1 3 2 4
1 4 2 3
2 3 1 4
2 4 1 3
3 4 1 2
Read 1 3 2 4: up from 1 to 3, down from 3 to 2, up from 2 to 4. Five of the
twenty four orderings zigzag.
## What most people try first
Produce every ordering and test the pattern afterwards. The test is a single
pass, so it feels cheap, and the problem is the orderings: at n = 8 that is
40320 leaves to find 1385 answers, and the share that survives keeps falling as
n grows.
A different and more interesting first attempt is to try to build the answer greedily: sort, then interleave the small half and the large half. That produces ONE zigzag ordering and this problem asks for all of them, which is the usual reason a greedy construction is the wrong tool here. Worth knowing it exists, because it is the right answer to "give me any zigzag ordering".
## The method
The pattern is a rule about each value and the one before it, so it is a push-time test. The only thing to get right is which direction applies, and that is decided by the position being filled:
go():
pos = size(cur)
if pos == n: record cur; return
for i in 0 .. n-1:
if used[i]: continue
if pos > 0:
if pos is odd and not a[i] > last(cur): continue
if pos is even and not a[i] < last(cur): continue
place a[i], recurse, take it back
Position 0 has nothing before it and is unconstrained. Position 1 must go up, position 2 down, and the parity of the position decides it from then on.
## Why it is correct
The zigzag condition is a conjunction of one comparison per neighbouring pair,
and the ordering is built left to right, so the comparison for the pair ending
at position pos is settled when position pos is filled and never changes.
Testing it there tests each clause exactly once, so a leaf is reached precisely
when every clause holds.
The direction must come from the POSITION and not from a flag that flips on each successful push. A flag works too, but it has to be restored on the way out like any other piece of state, and forgetting that is the characteristic bug. The position already carries the information, so there is nothing to restore.
## 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.
## Is the answer ever empty?
No, and that is settled here rather than left open. For any set of distinct
values a zigzag ordering exists: sort them, then take the smallest, the largest,
the second smallest, the second largest, and so on. Every step alternates
between a value below everything taken from the top and a value above everything
taken from the bottom, so the comparisons alternate as required. So none is
never printed, and n = 1 prints its single ordering, which zigzags because
there is no pair to check.
## Cost
Proportional to the number of zigzag orderings times O(n) to print. The count
is 1385 at n = 8, against 40320 orderings.
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 zigzag ordering on its own line, values separated by single spaces, the lines ordered as described. At least one always exists, so none is never printed.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.