How to prove the transitivity of the comparator?


  • 2
    Y

    The solution can't be correct without the transitivity:

    If AB > BA and BC > CB, then we have AC > CA.

    But how to prove it?


  • -1
    L

    What I have is:

    1)   AB > BA
    2)   BC > CB
    

    from 2) we have

    3)   BAC > CAB
    

    from 1) we have

    4)  BAC > CAB > CBA
    

    from 1) we also have

    5) ABC > BAC > CAB > CBA
    

    from 5 and "take out" the B we have

    6) AC > CA
    

    Glad you asked this, even after showing this property, I'm still not sure why this "sorting" solution works.

    EDIT: Just realized I didn't prove that AB > BA => ACB > BCA. I believe that inequality is true. Don't want to prove it at the moment.

    EDIT2 : Realized what I said above is wrong too. My intuition is really not helping me for this problem.


  • 0
    H

    that's my concern too, I don't know why someone just take it for granted, although it seems correct, but I can't prove it


  • 0

  • 0
    Y
    1. BAC > CAB let's take A 999, B70078, C7007, this assertion is not correct

Log in to reply
 

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