Mathematical proof of correctness of sorting method


  • 24
    C
    string largestNumber(vector<int>& nums) {
            vector<string> vs;
            string s="";
            for(int &num:nums)  vs.push_back(to_string(num));
            sort(vs.begin(),vs.end(),[](string a,string b){return a+b>b+a;});
            if(vs[0][0]=='0') return "0"; //deal with all "0" value
            for(string & ss:vs)  s+=ss;
            return s;
        }
    

    Why does this solution work?

    First, we need to show the comparator works, or the array is sortable. Meaning if A comes before B and B comes before C, then A must comes before C.

    Next, we must prove after sorting, by concatenating the array,we get the largest number.

    The first proof is by @19thhell.

    Let A, B, C be the integer given. To concatenate A and B into AB, we need to know how many digits are there in B, then multiply power of 10 with A, add B to the result. Example: 12312 = 123 * 100 + 12. The number of digits in B is lgB + 1, therefore we need to multiply A with 10^(lgB + 1), then add the result with B to get AB. Now we can start our proof.

    Proof:
    
        Let us define f(X) = 10^(lgX + 1), then XY = f(Y)X + Y
    
        If AB <= BA, then we have
        f(B)A + B <= f(A)B + A
        (f(B) - 1)A <= (f(A) - 1)B
        that is
        A <= B·(f(A) - 1) / (f(B) - 1)   (1)
    
        If BC <= CB, then we have
        f(C)B + C <= f(B)C + B
        (f(C) - 1)B <= (f(B) - 1)C
        that is
        B <= C·(f(B) - 1) / (f(C) - 1)   (2)
    
        Combine (1), (2), we have
        A <= C·(f(A) - 1) / (f(C) - 1)
        (f(C) - 1)A <= (f(A) - 1)C
        f(C)A + C <= f(A)C + A
        AC <= CA
    

    The second proof:

    First, some properties. (IF THE IMAGE BELOW IS NOT SHOWN PROPERLY, OPEN IT IN ANOTHER WINDOW OR DOWNLOAD IT)
    enter image description here

    enter image description here


  • 0
    P

    A valid proof is always more valuable than a concise, fast, short solution for me. Thanks so much!


  • 0
    Z

    You are a genuis


  • 0
    B

    thank you so much for this detailed and clear proof! more people should be upvoting this. That there are so few people viewing this makes me wonder whether people just assume top post algorithms to have correct behavior, or if they figured out the proof themselves...


  • 2
    C

    Really nice proof!
    To make the post easier to understand:
    f(X) = 10^(lgX + 1) means that f(X) is the number of digits in number X, e.g. f(1) = 1, f(9) = 1, f(10) = 2
    The post also didn't strictly distinguish between "string concatenation" and "multiplication", e.g.
    "then XY = f(Y)X + Y" means:
    concat(X,Y) = f(Y) * X + Y

    The main idea of second proof is:
    When you have a sorted sequence A, B, C, D, ..., then A must be the first part of the largest number. This can be proved by contradiction:
    If A is not the first part of the largest number, then the largest number would be something like X....XAX....X (X represents other numbers). You can obtain a number no smaller than itself by swapping A with the number preceding it. You can continue this process until A becomes the first part of the number, and this number is larger than "the largest number", leading to a contradiction. (Note that the last swap that make A the first part of the number guarantees to increase the number, because the assumption "A is not the first part of the largest number")


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.