2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.