1163. Orderings With No Forbidden Pair Side by Side

Given n distinct values and f forbidden pairs, print every ordering of all the values in which no forbidden pair stands next to each other.

A forbidden pair is unordered: if 1 2 is forbidden, then neither 1 2 nor 2 1 may appear as neighbours anywhere in the ordering.

3 1 1 2 3 1 2 -> 1 3 2 2 3 1

Four of the six orderings put 1 next to 2 and are out. 1 3 2 keeps them apart.

## What most people try first

Build every ordering and then scan it for a forbidden neighbouring pair. It is correct and it tests the same prefix over and over: every ordering starting 1 2 is rebuilt and rejected, and there are (n-2)! of them. At n = 8 that is 720 leaves built for each dead prefix of length two.

## The method

The rule only ever involves the value being placed and the value immediately before it, so it can be checked at the push:

go(): if size(cur) == n: record cur; return for i in 0 .. n-1: if used[i]: continue if cur is not empty and {last(cur), a[i]} is forbidden: continue used[i] = true; cur.push(a[i]) go() cur.pop(); used[i] = false

A refused push removes everything below it, so a dead prefix of length L costs one test instead of (n - L)! leaves.

## Why it is correct

Every neighbouring pair of the finished ordering is tested exactly once, at the moment the later of the two values is pushed, and nothing else is ever tested. So a leaf is reached precisely when no neighbouring pair is forbidden, which is precisely the condition asked for. The constraint is LOCAL in this sense, and that is what makes checking it at the push both cheap and complete. Had the rule been about any two values at distance two, the same trick would need the last two values rather than the last one, and had it been about the whole ordering, such as "the total of neighbouring differences is at most t", no push-time test could be complete at all.

## Looking up a forbidden pair

With f at most 20 a linear scan of the pair list is 20 comparisons and perfectly adequate. For a larger f the usual move is a lookup keyed by the pair, which turns the test into one probe. The point is that the test is O(1) or close to it, because it runs once per push and the pushes are the search.

## 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 boundaries that must be settled

A pair may be listed with its two values in either order, and may be listed twice; both mean the same thing. f = 0 forbids nothing, so the answer is every ordering. And the answer may genuinely be empty: forbid all three pairs of three values and no ordering survives, so the output is none. All three are in the tests.

## Cost

Proportional to the number of surviving orderings times O(n), plus the pruned tests. At n = 8 with nothing forbidden that is 40320 lines, so the constraint on n is set by the size of the output rather than by the search.

Constraints - `1 ≤ n ≤ 8` - `0 ≤ f ≤ 20` - `-1000 ≤ a[i] ≤ 1000` - All `n` values are distinct. - A pair may be listed in either order, and may be listed more than once.