Решен: «Метод сравнения нарушает его общий договор» - я не могу обнаружить любую интранзитивности

Question

Edit: почему я думаю, что это не дубликат: Как biziclop писал, что проблема здесь не интранзитивность (a>b & b>c => a>c) как и в других проблемах, упомянутых здесь , но что пункт a>b => -(b>a) нарушен, так что это другая проблема.

Я получаю следующее сообщение об ошибке:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract! 
at java.util.TimSort.mergeHi(Unknown Source) 
at java.util.TimSort.mergeAt(Unknown Source) 
at java.util.TimSort.mergeForceCollapse(Unknown Source) 
at java.util.TimSort.sort(Unknown Source) 
at java.util.Arrays.sort(Unknown Source) 
at construct.Repair.regretRepair(Repair.java:101) 
at lns.One.repaired(One.java:122) 
at lns.One.segment(One.java:68) 
at lns.One.lnsSolution(One.java:35) 
at lns.All.lnsSolutions(All.java:22) 
at barter.Genetic.initialPopulation(Genetic.java:36) 
at barter.Genetic.run(Genetic.java:26) 
at program.Main.main(Main.java:22) 

Это где это происходит:

Arrays.sort(regretProfits, new Comparator<RegretProfit>(){ 
      @Override 
      public int compare(RegretProfit first, RegretProfit second){ 
       if (first.possibleRoutes <= 0){ 
        if (second.possibleRoutes > 0){ 
         return 1; 
        } 
        return 0; 
       }     
       if (first.possibleRoutes < solution.schedule.size() - kay + 1){ 
        if (first.possibleRoutes < second.possibleRoutes){ 
         return -1; 
        } 
        if (first.possibleRoutes > second.possibleRoutes){ 
         return 1; 
        } 
        if (first.profit > second.profit){ 
         return -1; 
        } 
        if (first.profit < second.profit){ 
         return 1; 
        } 
       } 
       if (first.regret > second.regret){ 
        return -1; 
       } 
       if (first.regret < second.regret){ 
        return 1; 
       } 
       return 0; 
      } 
     ;}); 

И это класс, где определен объект RegretProfit:

public class RegretProfit { 
    public int[] order; 
    public double regret; 
    public double profit; 
    public int possibleRoutes; 
} 

Ошибка возникает только каждые несколько тысяч итераций. Я был бы очень благодарен, если бы у кого-то были идеи, в чем проблема. Я читал, что непереходность может вызвать это исключение, но я действительно не мог понять, где я, возможно, ошибся.

Решено, спасибо biziclop!

Arrays.sort(regretProfits, new Comparator<RegretProfit>(){ 
      @Override 
      public int compare(RegretProfit first, RegretProfit second){ 
       if (first.possibleRoutes <= 0 && second.possibleRoutes > 0){ 
        return 1; 
       } 
       if (first.possibleRoutes <= 0 && second.possibleRoutes <= 0){ 
        return 0; 
       } 
       if (first.possibleRoutes > 0 && second.possibleRoutes <= 0){ 
        return -1; 
       } 
       if (first.possibleRoutes < solution.schedule.size() - kay + 1 || second.possibleRoutes < solution.schedule.size() - kay + 1){ 
        if (first.possibleRoutes < second.possibleRoutes){ 
         return -1; 
        } 
        if (first.possibleRoutes > second.possibleRoutes){ 
         return 1; 
        } 
        if (first.profit > second.profit){ 
         return -1; 
        } 
        if (first.profit < second.profit){ 
         return 1; 
        } 
       } 
       if (first.regret > second.regret){ 
        return -1; 
       } 
       if (first.regret < second.regret){ 
        return 1; 
       } 
       return 0; 
      } 
     ;}); 

Answer 1

Это не транзитивность, что является ключевой проблемой здесь, часть контракта нарушенного является sgn(compare(x, y)) == -sgn(compare(y, x))

Если у вас есть эти записи, например:

first.possibleRoutes = -1; first.regret = 1 
second.possibleRoutes = 1; second.regret = -1 

Ваш компаратор возвращает 1 Но если вы их замените:

first.possibleRoutes = 1; first.regret = -1 
second.possibleRoutes = -1; second.regret = 1 

Ваш компаратор все еще по ssibly возвращает 1.

Глядя на код, есть два подозрительных, несимметричные конструкции:

  if (first.possibleRoutes <= 0){ 
       if (second.possibleRoutes > 0){ 
        return 1; 
       } 
       return 0; 
      } 

Здесь нет никакого соответствия -1 возвращения first и second перепутаны. Вы также рассматриваете каждый предмет с possibleRoutes <= 0 как равный, что, вероятно, не то, что вы хотите.

  if (first.possibleRoutes < solution.schedule.size() - kay + 1){ 

Здесь вы вводите ветку, основанную исключительно на стоимости first, что означает эта отрасль также может потенциально привести к sgn(compare(x, y)) != -sgn(compare(y, x)).

Конечно, возможно, что при дополнительных ограничениях всей системы две проблемы отменяют друг друга (очевидно, они не в этом случае), но это очень хрупкий способ проектирования компараторов, и я бы посоветовал вы убедитесь, что все ветви симметричны. Это значительно облегчает объяснение правильности вашего кода.