Rigorous Math proof for equivalence of Uniqueness property and Pair property


  • 0

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.