Team matchmaking respecting positions (untested, untried)

AutoMatchup.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

class AutoMatchup {

    /**
     * Assume that this exists somewhere
     */
    interface TrueSkill {
        int get1v1Quality(String playerA, String playerB);
    }

    /**
     * An imaginary 1v1 and the quality that this 1v1 would have
     */
    class Matchup1v1 {
        String playerA;
        String playerB;
        int quality;

        Matchup1v1(String playerA, String playerB, int quality) {
            // always save in same order so that order of given players does not matter
            this.playerA = playerA.compareTo(playerB) > 0 ? playerA : playerB;
            this.playerB = playerA.compareTo(playerB) <= 0 ? playerA : playerB;
            this.quality = quality;
        }

        boolean overlaps(Matchup1v1 other) {
            return other.contains(this.playerA) || other.contains(this.playerB);
        }

        boolean contains(String player) {
            return this.playerA.equals(player) || this.playerB.equals(player);
        }
        
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj instanceof Matchup1v1) {
                var other = (Matchup1v1) obj;
                return playerA.equals(other.playerA) && playerB.equals(other.playerB);
            }
            return false;
        }
        
        @Override
        public int hashCode() {
            return Objects.hash(playerA, playerB);
        }
    }

    /**
     * A team viewed as a number of imaginary 1v1s (one per position) and combined 1v1 qualities
     */
    class TeamComposition {
        Set<Matchup1v1> matchups = new HashSet<>();
        int combinedQualityOfMatchups = 0;
        
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            return obj instanceof TeamComposition && matchups.equals(((TeamComposition) obj).matchups);
        }
        
        @Override
        public int hashCode() {
            return matchups.hashCode();
        }
    }

    /**
     * Entry point
     */
    public TeamComposition getBestTeamMatchup(Set<String> players, TrueSkill trueSkill) {
        if (players.size() % 2 != 0) {
            throw new IllegalArgumentException("Number of players must be even");
        }
        // get all possible 1v1s and their qualities
        var all_1v1s = new HashSet<Matchup1v1>();
        for (var playerA : players) {
            for (var playerB : players) {
                if (!playerA.equals(playerB)) {
                    int qualityOfAvsB = trueSkill.get1v1Quality(playerA, playerB);
                    all_1v1s.add(new Matchup1v1(playerA, playerB, qualityOfAvsB));
                }
            }
        }
        // get all possible combinations of teams as multiple 1v1 matchups per composition
        Set<TeamComposition> compositions = createTeamCompositions(all_1v1s);
        // set quality for team compositions
        calculateCompositionQualities(compositions);
        // sort by quality and return last
        var sorted = new ArrayList<>(compositions);
        sorted.sort((a, b) -> Integer.compare(a.combinedQualityOfMatchups, b.combinedQualityOfMatchups));
        return sorted.get(sorted.size() - 1);
    }

    /*
     * Returns possible team compositions and (recursively adds more matchups to finish compositions).
     */
    private Set<TeamComposition> createTeamCompositions(Set<Matchup1v1> availableMatchups) {
        if (availableMatchups.size() == 1) {
            // if there is only one possible matchup, the team composition IS that matchup
            var result = new HashSet<TeamComposition>();
            var newComposition = new TeamComposition();
            newComposition.matchups.add(availableMatchups.iterator().next());
            return result;
        } else {
            Set<TeamComposition> result = new HashSet<>();
            // select a matchup from available
            for (var selected : availableMatchups) {
                // remove any matchups that have overlapping players with out selected matchup
                var remaining = new HashSet<Matchup1v1>(availableMatchups);
                removeOverlappingMatchups(selected, remaining);
                // recursively get team compositions for the remaining matchups (which now include
                // exactly two players less, the players from our selected matchup). If all players
                // except two were removed, only their matchup will be left and recursion stops.
                Set<TeamComposition> compositions = createTeamCompositions(remaining);
                // we add our selected matchup to all existing (unfinished) team compositions
                for (var composition : compositions) {
                    composition.matchups.add(selected);
                    result.add(composition);
                }
            }
            // do this for all possible selections to get all possible compositions
            return result;
        }
    }

    private void removeOverlappingMatchups(Matchup1v1 matchup, Set<Matchup1v1> target) {
        for (var i = target.iterator(); i.hasNext();) {
            if (i.next().overlaps(matchup)) {
                i.remove();
            }
        }
    }

    private void calculateCompositionQualities(Set<TeamComposition> compositions) {
        for (var composition : compositions) {
            composition.combinedQualityOfMatchups = 0;
            for (var single_1v1 : composition.matchups) {
                // could also be squared
                composition.combinedQualityOfMatchups += single_1v1.quality;
            }
        }
    }
}