World's most popular travel blog for travel bloggers.

Transitivity of concat comparison

, , No Comments
Problem Detail: 

I am trying to solve the problem of finding the permutation, amongst all possible ones, of an array of strings, where the concatenation of them compares smallest lexicographically. I solve it with an sort with the following comparison

def concat_cmp(x, y):     return cmp(x + y, y + x) 

+ is the string concat operator.

The solution passed all the test cases, but I cannot prove its correctness. Specifically, I cannot prove that this binary relation is transitive. Any help?

Asked By : Siyuan Ren
Answered By : Yuval Filmus

We denote the concatenation of $x$ and $y$ by $xy$. Your relation is $x \prec y$ iff $xy < yx$ (where $<$ is the lexicographic order). You want to show that $x \prec y \prec z$ implies $x \prec z$. Suppose therefore that $xy < yx$ and $yz < zy$. Our goal is to show that $xz < zx$.

Say that two strings $s,t$ are incompatible if neither is a prefix of the other. If $s \prec t$ and $s,t$ are incompatible then there is an index on which they differ, and the first such index $i$ satisfies $s_i < t_i$. Conversely, if there exists an index on which $s,t$ differ and the first such index $i$ satisfies $s_i < t_i$ then $s,t$ are incompatible and $s \prec t$.

The proof is by induction on $|x|+|y|+|z|$. We consider several cases.

Case 1. $x,y$ are incompatible, and $y,z$ are incompatible. Let $i$ be the first index on which $x,y$ differ, and let $j$ be the first index on which $y,z$ differ. Then $k = \min(i,j)$ is the minimal index on which $x,z$ differ and $x_k < z_k$, implying $x \prec z$.

Case 2. $x = yw$. In this case $xy < yx$ implies $ywy < yyw$, and so $w \prec y$. Induction shows that $w \prec z$, and so $xz = ywz < yzw < zyw = zx$.

Case 3. $z = yw$. In this case $yz < zy$ implies $yyw < ywy$, and so $y \prec w$. Induction shows that $x \prec w$, and so $xz = xyw < yxw < ywx = zx$.

Case 4. $x = zw$. In this case $xy < yx$ implies $zwy < yzw < zyw$, and so $w \prec y$. Induction shows that $w \prec z$, and so $xz = zwz < zzw = zx$.

Case 5. $z = xw$. In this case $yz < zy$ implies $xyw < yxw < xwy$, and so $y \prec w$. Induction shows that $x \prec w$, and so $xz = xxw < xwx = zx$.

Case 6. $y = xw$ and $x,z$ are incompatible. In this case $xy < yx$ implies $xxw < xwx$, and so $x \prec w$. Moreover, $yz < zy$ implies $xwz < zxw < zwx$. Since $x,z$ are incompatible, there exists an index on which they differ, and the minimal such index $i$ must satisfy $x_i < z_i$. It follows that $x \prec z$.

Case 7. $y = zw$ and $x,z$ are incompatible. In this case $yz < zy$ implies $zwz < zzw$, and so $w \prec z$. Moreover, $xy < yx$ implies $xwz < xzw < zwx$. Since $x,z$ are incompatible, there exists an index on which they differ, and the minimal such index $i$ must satisfy $x_i < z_i$. It follows that $x \prec z$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56480

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback