排列数字以形成最大数 - 算法证明

Question

众所周知 algorithmic problem，给定数字数组，例如[1, 20, 3, 14] 以尽可能形成最大数的方式排列数字，在本例中为 320141。

SO 和其他站点上有很多解决方案，使用以下算法：

String[] strs = new String[nums.length];
for(int i=0; i<nums.length; i++){
    strs[i] = String.valueOf(nums[i]);
}

Arrays.sort(strs, new Comparator<String>(){
    public int compare(String s1, String s2){
        String leftRight = s1+s2;
        String rightLeft = s2+s1;
        return -leftRight.compareTo(rightLeft);

    }
});

StringBuilder sb = new StringBuilder();
for(String s: strs){
    sb.append(s);
}

return sb.toString();

它确实有效，但我找不到该算法的正式证明。 quora 上有一个答案，但我不会称其为正式证明。

谁能给我一张证明草图或参考一些书或文章？如何从原始问题得到这个解决方案？

PS我试图解决原来的问题，但我的解决方案是错误的，我无法正确解决，现在我无法完全理解解决方案。

Answer 1

这是算法的草图。对于您给定的列表：

[1, 20, 3, 14]

想一想如何找到最大的串联数。

对于最重要的数字，选择具有最大初始数字的数字。（在示例中，选择 3，然后选择 20。因此答案以 320 开头。）

其余数字1和14的首位数字相同（即1）。接下来选哪个？这是算法的核心，compare 函数发挥作用的地方。它将构建数字并比较哪个在词汇上更大，即 114 与 141。return 语句中的负号将确保较大的数字在前。所以答案是 320141。

（该算法实际上并不比较初始数字，而是将字符串从词法上从最大到最小排序。）

Answer 2

关于符号：我将使用竖线分隔数字，所以它是更容易看到数字序列和 结果数字 在同时：3|20|14|1

让我们暂时假设关系——我们称它为 R 由 <= 运算符表示——由比较定义函数是一个全序。由表达式

决定

-(a+b).compareTo(b+a)

需要注意的一件重要事情是，这种关系不仅影响两个数字 a 和 b 被孤立地考虑但也告诉我们一些事情关于两个数字嵌入的结果数字：

如果a<=b，则x|a|b|y <= x|b|a|y

其中 x 和 y 是任意长度。换句话说：如果我们有一个数字序列我们将两个相邻的数字 a 和 b 与 a<=b 交换，结果之后数字将大于或等于。

示例：3|14|20|1 <= 3|20|14|1 因为 14 <= 20

我们现在可以假设解决方案不是唯一的我们的关系 R 暗示了一个矛盾：让我们假设解决方案是一些不符合 R 的特定序列。因为 R 是一个总顺序，我们可以通过交换重新排列数字以匹配 R 相邻元素直到顺序符合R。这种重新排序可以与冒泡排序进行比较。但是，在每个交换操作中引导我们进入新秩序，由此产生的数量增加！这是显然是矛盾的，所以原来的顺序不可能是解决方案。

剩下的就是R是一个全序，即传递的，反对称的和总的。既然你要了草图证明，我会省略这部分。关键部分是证明传递性，即

a <= b 和 b <= c 意味着 a <= c。

排列数字以形成最大数 - 算法证明

arrange numbers to form largest number - proof of algorithm

algorithm

proof