How can I sort using a comparator with ties broken randomly?

Question

I'm building a program that simulates a sports league, and, oftentimes, I want to sort teams by points, goal differential, etc. to determine things like which team gets promoted or which team gets preferential seeding in a tournament. But, sometimes, teams will be tied on all the criteria that I want to use, and I would like those ties to be broken randomly. I was previously using teams' ids (which are unique ints) to break ties, but I'd like to make it so that no team gets consistent preferential treatment in this sorting. I know that if I just let Java decide which of the tied teams will be placed in front of the other, it'll be very unpredictable, but I don't trust it to be actually random, and I'm worried that it'd inadvertently give some teams an advantage.

I've been using Collections.sort() with comparators to do my sorting, and I recently just went for it, and switched my comparators to use a random number as the final tiebreaker rather than the team ids. Here is the comparator in question:

public static final Comparator<Team> pointsGDRand = new Comparator<Team>() {
    public int compare(Team a, Team b) {
        int result = b.getStats().getPts() - a.getStats().getPts();
        if (result == 0) {
            result = b.getStats().getGD() - a.getStats().getGD();
            if (result == 0) {
                result = R.boolNum();
            }
        }
        return result;
    }
};

I think the getter functions are self explanatory, but here's that random function:

public static int boolNum() {
    return r.nextBoolean() ? 1 : -1;
}

But, just a bit ago (it look a long time for this error to pop up), I got this error:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!

I've read a little bit, and I think that the problem is likely that I had some instance where it figured out that A > B and B > C, but also A < C. This sheds some light on why it took so long for this error to pop up (it did maybe 20,000 sorts before it popped up with this error), because 2 teams getting the exact same score on all criteria seems like a pretty rare occurrence to me, much less 3 or more.

I'd rather not write my own custom sort, and I'd also rather not shuffle the list in question before each time I sort it (I feel like that'd be inefficient, but I'm confident it would work).

So, how can I make a comparator that breaks ties randomly (such that there's no risk of a team winning tiebreaks disproportionately) without risking that same error again?

Answer 1

Here's a different approach for randomly choosing tied teams

Use a map.

• store the teams that tied in a map, keyed by their score. The map can be a tree map so it can be sorted.
• then iterate over the map and pick a team at random from each list.

Here are the teams before any processing. The output is score and team name.

[3, A]
[1, B]
[2, C]
[0, D]
[0, E]
[1, F]
[1, G]
[2, H]
[2, I]
[2, J]

Now build the team map.

Map<Integer, List<Team>> team = teams.stream().collect(
   Collectors.groupingBy(t->t.getStats().getPts(),
        ()->new TreeMap<Integer,List<Team>>(Comparator.reverseOrder()),
            Collectors.toList()));

Here is the map of the teams, sorted in descending order of score. The key is the score and the value is a list of teams with that score.

3=[[3, A]]
2=[[2, C], [2, H], [2, I], [2, J]]
1=[[1, B], [1, F], [1, G]]
0=[[0, D], [0, E]]

Now, just pick a random value from each list for a given score. This picks a value between 0 and the number of values in the list (i.e. size())

Random r = new Random();
for (Entry<Integer, List<Team>> e : team.entrySet()) {
    int pick = r.nextInt(e.getValue().size());
    System.out.println(e.getKey() + " " + e.getValue().get(pick));

for this run printed

3 [3, A]
2 [2, C]
1 [1, B]
0 [0, E]