题记

这是一个大学上郭老的算法课时第一次遇到的问题，很老了。后来又在网上各种面试题中看到，但所有地方都只给出了答案，并没给出证明。我自己还写过一个证明（见本文末尾），但最近翻看时觉得有问题，所以这里又重新补充一个正解。

问题

给N个字符串s1, s2, …, sn，问怎样把它们连接起来使得得到的字符串字典序最小。

解答

以\(+\)表示字符串连接，\(\le_{lex}\)表示字符串字典序的小于等于关系。定义非严格偏序关系\(\le_{concat}\)为：\(A\le_{concat}B\)当且仅当\(A+B\le_{lex}B+A\)。则按照\(\le_{concat}\)这种序来排序所有串后按照结果的顺序把所有串逐个连接起来得到的串正好满足要求。

证明

先证明\(\le_{concat}\)是良定义的。注意这是一种非严格偏序而不是严格偏序。因此需要证明三个性质：

• 自反性：显然对任何\(s\)有\(s\le_{concat}s\)，因为\(s+s\le_{lex}s+s\)。
• 反对称性：若\(a\le_{concat}b\)且\(b\le_{concat}a\)，即\(a+b\le_{lex}b+a\)且\(b+a\le_{lex}a+b\)，说明\(a+b\)和\(b+a\)是同一个串，故\(a=_{concat}b\)（注意不一定有\(a=b\)，也可以是一个串是另一个串的多次重复。见下面\(prop\)函数的性质）。
• 传递性：设\(a\le_{concat}b\)且\(b\le_{concat}c\)，我们来证明\(a\le_{concat}c\)。令\(len(x)\)表示串\(x\)的长度。设字母表的大小为\(Z\)，我们把每个串使用\(Z+1\)进制计数法编码成一个\((0,1)\)之间的小数（本文最后会说明为什么不能编码为整数），记为\(val(x)\)。例如，对于由小写英文字母组成的串，有\(Z=26\)，对任意串如\(\text{"abcd"}\)有\(val(\text{"abcd"})=1*27^{-1}+2*27^{-2}+3*27^{-3}+4*27^{-4}=0.0399404632\cdots\)。用\(Z+1\)进制而不用\(Z\)进制是因为要用\(0\)来表示串末尾“不存在”的字符，因此每个串都可以看成末尾有无限个“不存在的字符”。很容易证明\(a\le_{lex}b\)等价于\(val(a)\le val(b)\)，这里略去。因此，\(a\le_{concat}b\)等价于\(a+b\le_{lex}b+a\)，而后者等价于\(val(a)+val(b)*(Z+1)^{-len(a)-1}\le val(b)+val(a)*(Z+1)^{-len(b)-1}\)也即\(\frac{val(a)}{1-(Z+1)^{-len(a)-1}}\le\frac{val(b)}{1-(Z+1)^{-len(b)-1}}\)（注意分母总是大于0的，因此移项时小于等于号方向不变）。注意，不等号两边的值只与每个串自身有关，因此是串的一个性质！定义\(prop(a)=\frac{val(a)}{1-(Z+1)^{-len(a)-1}}\)，则\(a\le_{concat}b\)等价于\(prop(a)\le prop(b)\)，而\(b\le_{concat}c\)等价于\(prop(b)\le prop(c)\)，因此若两者都成立我们显然有\(prop(a)\le prop(c)\)，它等价于\(a\le_{concat}c\)。

这就证明了这个序是一个非严格偏序，因此可以用来排序。现在来证明为什么按照排序后结果来连接得到的字符串字典序最小。证明过程用数学归纳法，非形式化地可以描述为：设\(a\)和\(b\)是排序后按照\(\le_{concat}\)关系“最小”（即排在最前面）的两个串，这说明\(a+b\le_{lex}x+y\)，其中\(x\)和\(y\)是任意两个串的其他组合（即可以其中一个是\(a\)或\(b\)但不能就是\(a\)和\(b\)）；

• 如果等号不成立，说明用\(a+b\)作为前缀得到的结果串显然会比使用其他组合作为前缀得到的结果串有更小的字典序；

• 如果等号成立，说明\(x\)、\(y\)和\(a\)、\(b\)有相同的\(prop\)值，因此它们相互的顺序如何并不重要！

  证明：设\(a+b=_{lex}x+y\)，这说明\(val(a+b)=val(x+y)\)，又根据排序的结果我们有\(prop(a)\le prop(b)\le prop(x)\le prop(y)\)，其中\(prop(x)\le prop(y)\)是因为\(x+y\)和\(a+b\)一样都是任意两串排列中字典序最小的，因此不可能有\(prop(y)\lt prop(x)\)。现在我们考虑只连接\(a\)、\(b\)、\(x\)、\(y\)四个串的问题，显然只对它们排序得到的结果顺序和原问题结果中它们之间的相对顺序是一样的（因为\(prop\)是每个串独有的性质和其他串无关）；但是，由于设\(a+b=_{lex}x+y\)，因此把\(x+y\)放前面而\(a+b\)放后面得到的串是一样的，都是最小，这说明\(prop(x)\le prop(y)\le prop(a)\le prop(b)\)，从而有\(prop(a)=prop(b)=prop(x)=prop(y)\)。这是一个很神奇的结论，它更本质的意义下文会进一步探讨。

综上，把\(a\)放在前面可以使结果字典序最小。现在把\(a\)拿掉，递归地应用这个过程即可（正确的做法是从2个串往多个串进行归纳）。

\(prop\)函数的性质

首先补充定义两个相等关系：\(=_{lex}\)表示两个串字典序一样，也即两个串相等；\(=_{concat}\)表示两个串的两种连接方式得到的结果相同。我们现在来看看\(a=_{concat}b\)，即\(a+b=_{lex}b+a\)到底意味着什么。首先，如果\(len(a)=len(b)\)，显然\(a\)和\(b\)是同一个串，我们不考虑这种没什么意思的情况，假设\(n=len(a),m=len(b),m\gt n\)。令\(s[i:j]\)表示串\(s\)从第\(i\)个字符到第\(j\)个字符之间的子串。把\(a+b\)、\(b+a\)两个串并排地放在一起，我们可以看到\(b\)比\(a\)多出来的部分可以把\(a+b\)和\(b+a\)分成三对相等的段：

• \[a=_{lex}b[1:n]\]
• \[b[1:m-n]=_{lex}b[n+1:m]\]
• \[b[m-n+1,m]=_{lex}a\]

从而我们有：

也即\(a=_{concat}b[1:m-n]\)。看出来了吗？当\(m\gt n\)时，\(a=_{concat}b\)等价于\(a=_{concat}b[1:m-n]\)。这是不是跟最大公约数的辗转相除法有点像？没错，这正是辗转相除法，通过递归地应用这种方式，到最后一定会有两个串长度相等的时候，这时该长度就是原串\(a\)和\(b\)长度的最大公约数。当\(a\)和\(b\)长度相等时这也显然。这说明，\(a=_{concat}b\)的充要条件是，它们均由长度等于它们俩长度的最大公约数的串重复多次得到。

现在形式化地写出上面提到的几个函数的定义：

1. \[val(s_1s_2s_3\cdots s_n)=\sum_{i=1}^{n}\big(s_i*(Z+1)^{-i}\big), s_i\in\{1,2,\cdots,Z\}\]
2. \[prop(s_1s_2s_3\cdots s_n)=\frac{val(s_1s_2s_3\cdots s_n)}{1-(Z+1)^{-n-1}}=\frac{\sum_{i=1}^{n}\big(s_i*(Z+1)^{-i}\big)}{1-(Z+1)^{-n-1}}, s_i\in\{1,2,\cdots,Z\}\]

因此，\(prop(s_1s_2s_3\cdots s_n)=prop(t_1t_2t_3\cdots t_m)\)的唯一解，就是：

• \[s_i=s_{i+\gcd(m,n)}, i\in\{1,2,\cdots,n-\gcd(m,n)\}\]
• \[t_j=t_{j+\gcd(m,n)}, j\in\{1,2,\cdots,m-\gcd(m,n)\}\]
• \[s_k=t_k,k\in\{1,2,\cdots,\gcd(m,n)\}\]

参考

• 一个貌似是Facebooker的博客，没看完，证明貌似只是在举例，不知有没有问题
• 自己以前写的博文。里面的证明是错误的，原因就在于，实际上我们无法用正整数来编码这些串，使得\(a\le_{lex}b\)当且仅当\(val(a)\le val(b)\)，其中\(val\)是值域为整数的函数。否则，假设这样的编码方法\(val\)存在，设问题考虑的是英文小写字母组成的串，则\(val(\text{"b"})\)是一个确定的值，但是由于比串\(\text{"b"}\)字典序小的串有无限多个（\(\text{"a","aa","aaa",}\cdots\)），矛盾。