排列数字以形成最大数字-算法证明 [英] arrange numbers to form largest number - proof of algorithm
问题描述
存在已知的算法问题，并给出了数组数量，例如 [1、20、3、14] 排列数字的方式应使它们形成最大的数字，在这种情况下为 320141 .
There is well known algorithmic problem, given array of numbers e.g. [1, 20, 3, 14] arrange numbers in such a way that they form biggest number possible, in this case 320141.
使用以下算法，SO和其他站点上有很多解决方案:
There is plenty of solutions on SO and other sites, using the following algorithm:
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 上有一个答案，但我不会将其称为正式证明.
It certainly works, but I cannot find a formal proof of this algorithm. There is one answer on quora, but I wouldn't call it a formal proof.
有人可以给我一个草图或参考一些书或文章吗?如何从最初的问题中获得这一解决方案?
Does anyone can give me a sketch of proof or reference some book or article? How one can get on this solution from the original problem?
PS，我尝试解决原始问题，但解决方案错误，无法正确解决，现在我无法完全理解解决方案.
PS I tried to solve original problem but my solution was wrong, I couldn't get it right, and now I could not fully understand solution.
推荐答案
关于符号:我将使用管道将数字分开，因此更容易看到数字序列和结果数字同时:3 | 20 | 14 | 1
Regarding notation: I will use pipes to separate the numbers so it's easier to see the sequence of numbers and the resulting number at the same time: 3|20|14|1
让我们暂时假设这种关系-我们称其为 R 由< = 运算符表示-由比较定义功能是总订单.由表达式决定
Let us assume for the moment that the relation -- let's call it R
represented by the <= operator -- that is defined by the compare
function is a total order. It is determined by the expression
-(a+b).compareTo(b+a)
直觉上说，如果我们有两个数字 a 和 b 和 b | a 是大于 a | b ， b 的排名应高于 a ，即出现在解决方案中 a 的左侧.如果 a | b 大于 b | a ，则采用另一种方法圆形的.如果 a | b = b | a ，则顺序无关紧要.
Intuitively it says that if we have two numbers a and b and b|a is larger than a|b, b should get a higher rank than a, i.e. it should occur left of a in the solution. If a|b is larger than b|a, it's the other way round. If a|b = b|a, the order does not matter.
需要注意的重要一件事是，这种关系不仅影响两个孤立地考虑的数字 a 和 b 还能告诉我们一些信息关于结果数字，两个数字将嵌入其中:
One important thing to note is that this relation not only affects two numbers a and b considered in isolation but also tells us something about the resulting number the two numbers are embedded in:
如果 a< = b ，则 x | a | b | y < = x | b | a | y
If a<=b, then x|a|b|y <= x|b|a|y
，其中 x 和 y 是任意长度.换句话说:如果我们有一个数字序列然后我们将两个相邻的数字 a 和 b 与 a< = b 交换，结果此后数字将更大或相等.
with x and y being numbers of arbitrary lengths. In other words: If we have a sequence of numbers and we swap two adjacent numbers a and b with a<=b, the resulting number will be greater or equal afterwards.
示例: 3 | 14 | 20 | 1< = 3 | 20 | 14 | 1 ，因为 14< = 20
我们现在可以得出这样的假设:解决方案不是一个我们的关系 R 暗示矛盾:让我们假设解决方案是某些不符合 R 的特定序列.由于 R 是一个总订单，我们可以通过交换来重新排列数字以匹配 R 相邻元素，直到顺序符合 R .这种重新排序可以被比作泡沫排序.但是，在每个交换操作中导致我们到达新订单，结果数量增加了！这是显然是矛盾的，所以原始顺序不能是解决方案.
We can now lead the assumption that the solution is not the one implied by our relation R to a contradiction: Let's assume the solution is some specific sequence not conforming to R. Since R is a total order, we can rearrange the numbers to match R by swapping adjacent elements until the order conforms to R. This reordering can be compared to a bubble sort. However, in each swap operation that leads us to the new order, the resulting number increases! This is clearly a contradiction, so the original order cannot be the the solution.
剩下要显示的是 R 是总订单，即可传递的，反对称的和完全的.由于您要求提供草图证明，我将省略此部分.必不可少的部分是证明可传递性，即那个
All that is left to show is that R is a total order, i.e. it is transitive, antisymmetric and total. Since you asked for a sketch of the proof, I'll omit this part. The essential part is proving transitivity, i.e. that
a< = b 和 b< = c 表示 a< = c .
这篇关于排列数字以形成最大数字-算法证明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
