algorithm - 如何证明 "Arrange given numbers to form the biggest number"算法的正确性？

Question

Arrange given numbers to form the biggest number给出算法。它用下面的文字来证明算法的正确性:

So how do we go about it? The idea is to use any comparison based sorting algorithm. In the used sorting algorithm, instead of using the default comparison, write a comparison function myCompare() and use it to sort numbers. Given two numbers X and Y, how should myCompare() decide which number to put first – we compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y). If XY is larger, then X should come before Y in output, else Y should come before. For example, let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542. Since 60542 is greater than 54260, we put Y first.

考虑三个数字:X、Y 和 Z。使用 X -> Y 表示 X 应该在 Y 之前。基于比较的算法可以使用以下两个比较将 X、Y 和 Z 排序为 XYZ: XY >= YX => X -> Y 和 YZ >= ZY => Y -> Z。但是这两次比较并不能保证XYZ是最大的数。换句话说，X 应该在 Y 之前和 Y 应该在 Z 之前的事实不一定确保XYZ 构成最大的数字。以YZX为例。要证明 XYZ >= YZX，我们需要证明 X(YZ) >= (YZ)X 这意味着 X 应该在 YZ作为一个整体组成一个更大的数。

谁能给出算法正确性的正式证明？

Answer 1

首先我们要证明如果X"<"Y和Y"<"Z则X"<"Z。假设他们分别有p,q和r位，前两个关系简化为

• X * 10^q + Y ≥ Y * 10^p + X ⇒ X * (10^q - 1) ≥ Y * (10^p - 1)
• Y * 10^r + Z ≥ Z * 10^q + Y ⇒ Y * (10^r - 1) ≥ Z * (10^q - 1)

我们要证明

• X * 10^r + Z ≥ Z * 10^p + X 等价于 X * (10^r - 1) ≥ Z * (10^p - 1)

但这可以简单地通过将前两个不等式相乘并抵消公共(public)项来证明。

既然我们已经证明该关系是可传递的(因此可以用来定义排序顺序)，那么很容易证明它可以解决问题。

假设给定的数字是 A, B, C … 这样 A "<"B "<"C "<"D...。我们将证明 A 必须在最后的数字中排在第一位。如果不是，我们有一个像 (some prefix)XA(some suffix) 这样的字符串作为最终数字。很容易，(一些前缀)AX(一些后缀)是一个更大的数字，因为由于传递性，所有 X 的“<”X。以这种方式继续，A 向左冒泡，直到它成为第一个元素。

现在我们已经确定了第一个元素，可以将相同的论证应用于 B 等等，以表明最佳解决方案是 ABCD...