Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
