Re: [Simple Solution : one-pass](using only array (C++ 92ms)

@jeffery To translate this into rigorous math statement:

Given a finite sequence `{a[n]}`

and a finitely set of finite sequences `{sub[k][n]}`

, where each `{sub[k][*]}`

is a subsequence of `{a[n]}`

. Prove that the following properties are equivalent:

**Uniqueness property**: there does not exist another permutation`{a'[n]}`

of`{a[n]}`

such that each`{sub[k][*]}`

is also a subsequence of the permutated`{a'[n]}`

.**Pair property**: every adjacent pair`a[i], a[i+1]`

shows up in some subsequence`{sub[k][*]}`

.

Proof: Both derivation directions can be proved by contradiction.

**Pair property**=>**Uniqueness property**: Suppose we have a permutated `{a'[n]}`

to be the super sequence of each `{sub[k][*]}`

. Since it is permutated, there must exist some adjacent pair `a[i], a[i+1]`

from `{a[n]}`

such that `a[i+1]`

comes before `a[i]`

in `{a'[n]}`

. But we know the pair `a[i], a[i+1]`

shows up in some `{sub[k][*]}`

, so this `{sub[k][*]}`

cannot be a subsequence of `{a'[n]}`

.

**Uniqueness property**=>**Pair property**. Suppose there exists some adjacent pair `a[i], a[i+1]`

from `{a[n]}`

which does not show up in any `{sub[k][*]}`

. Then we can define `{a'[n]}`

to be same as `{a[n]}`

except that only `a[i], a[i+1]`

swapped. Note that any other `a[k]`

(`k!=i, k!=i+1`

) still has the same relative order in `{a'[n]}`

compared with `{a[n]}`

, so each `{sub[k][*]}`

must also be a subsequence for `{a'[n]}`

, and this violates the uniqueness property.

Proof is complete.