1160. Every Ordering When Values Repeat

Given n integers which may REPEAT, print every distinct ordering of all of them.

Two orderings are the same if they read the same left to right. 1 2 2 has three distinct orderings, not six:

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

## What most people try first

Run the search of problem 1147, which tries every unused POSITION at every step, and put the finished lines in a set. The six leaves collapse to three and the answer is right.

The ratio is what kills it. For n values with multiplicities m1, m2, ... the search builds n! leaves and there are n! / (m1! * m2! * ...) distinct answers. Eight copies of one value is 40320 leaves and one answer. The set is throwing away work that was expensive to produce, and the amount thrown away grows without bound as the input gets more repetitive.

## The rule, and the one word that makes it work

Sort, so equal values are adjacent. Now consider one call of the search, filling one position. Among the unused positions there may be several holding the same value, and choosing any of them puts the same value here and leaves the same multiset behind, so those branches are identical. Keep one.

Which one? The FIRST unused copy. Written out:

for i in 0 .. n-1: if used[i]: skip if i > 0 and a[i] == a[i-1] and not used[i-1]: skip place a[i] here, recurse, take it back

The second test is the whole problem. a[i] == a[i-1] and not used[i-1] says: an equal copy sits immediately before me and is still free, so I am not the first free copy and my subtree is a repeat of the one that uses it.

Dropping not used[i-1] turns the rule into "never use the second copy of a value at all", which cannot place 2 2 anywhere and loses most of the answers. Keeping it but writing used[i-1] instead inverts the choice of which copy to keep and loses answers in a different pattern. Both are in the tests.

## Why it is correct

Reached at least once. Take a distinct ordering. Build it by always filling the current position from the EARLIEST unused position holding the value that ordering wants there. At that moment no equal copy sits earlier and unused, so the skip test is false and the branch is open.

Reached at most once. Two paths that first differ at some position chose different i there. If a[i1] != a[i2] the orderings differ at that position. If a[i1] == a[i2] with i1 < i2, then at the moment of choosing, i2 had an equal unused copy at i2 - 1 or an equal copy further back, and in either case the skip test would have refused i2. So that case cannot arise.

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

Every input of at least one value has at least one ordering, so none is never printed here.

## Cost

Proportional to the number of distinct orderings times O(n) to print each, plus one skipped test per duplicate branch. At n = 8 with all values distinct that is 40320 lines.

Constraints - `1 ≤ n ≤ 8` - `-1000 ≤ a[i] ≤ 1000` - Values may repeat.