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.
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();
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 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.
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
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)
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.
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:
If a<=b, then x|a|b|y <= x|b|a|y
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.
Example: 3|14|20|1 <= 3|20|14|1 because 14 <= 20
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.
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 and b <= c implies a <= c.