0

I'm about to create an algorithm for football match scheduling. Main scheduling rules (as far as I know) are:

  1. There is an even number of teams
  2. One season consists of 2 rounds
  3. In one match day every team plays exactly one match
  4. Home teams in previous matchday should be an away team in next matchday (if it's possible - I looked at Serie A fixture, and there's an exlusion for this rule - every team plays 2 times in a row as (home/guests - first round/ revenge round) in one season
  5. There are 2 rounds and the rule is as follows: first match in first round (matchday 1) team A plays with team B (A:B), so the revenge match B:A should take place in - matchday allMatchDays/2 + i, where i = 1

Current approach:


  private static Map<Integer, List<Match>> createSchedule(/*Set<Team> allTeams*/) {

    Set <Team> allTeams = Set.of(

            Team.builder().name("A").build(),
            Team.builder().name("B").build(),
            Team.builder().name("C").build(),
            Team.builder().name("D").build(),
            Team.builder().name("E").build(),
            Team.builder().name("F").build(),
            Team.builder().name("G").build(),
            Team.builder().name("H").build(),
            Team.builder().name("I").build(),
            Team.builder().name("J").build()

    );

    int teamsNumber = allTeams.size();
    int matchDays = (teamsNumber - 1) * 2;
    int gamesNumberPerMatchDay = teamsNumber / 2;

    List<Match> allMatches = allTeams.stream()
            .map(team ->
                    allTeams.stream().filter(otherTeam -> !otherTeam.equals(team))
                            .map(otherTeam -> Match.builder().homeTeam(team)
                                    .awayTeam(otherTeam).build()).collect(Collectors.toList())
            )
            .flatMap(Collection::stream)
            .collect(Collectors.toList());

    Map<Integer, List<Match>> schedule = IntStream.rangeClosed(1, matchDays)
            .boxed()
            .collect(Collectors.toMap(
                    matchDay -> (Integer) matchDay,
                    matchDay -> new ArrayList<>()));

    Set<Team> homeTeamsInCurrentMatchDay = new HashSet<>();
    List<Team> teamsScheduledForCurrentMatchDay = new ArrayList<>();

    /*matchDay*/
    for (int i = 1; i <= matchDays / 2; i++) {

        List<Team> homeTeamsInPreviousMatchDay = new ArrayList<>(homeTeamsInCurrentMatchDay);
        homeTeamsInCurrentMatchDay.clear();

        /*match number in current Matchday*/
        for (int j = 1; j <= gamesNumberPerMatchDay; j++) {

            /*first match*/

            Match match = drawMatch(allMatches, teamsScheduledForCurrentMatchDay, homeTeamsInPreviousMatchDay);

            allMatches.remove(match);

            schedule.get(i).add(match);

            homeTeamsInCurrentMatchDay.add(match.getHomeTeam());

            teamsScheduledForCurrentMatchDay.add(match.getHomeTeam());
            teamsScheduledForCurrentMatchDay.add(match.getAwayTeam());

            /*revenge match*/

            Match revengeMatch = Match.builder().homeTeam(match.getAwayTeam()).awayTeam(match.getHomeTeam()).build();

            schedule.get((matchDays / 2) + i).add(revengeMatch);

            allMatches.remove(revengeMatch);

        }
        teamsScheduledForCurrentMatchDay.clear();
    }

    return schedule;
}

private static Match drawMatch(List<Match> matches, List<Team> alreadyScheduledTeamsInCurrentMatchDay, List<Team> homeTeamsInPreviousMatchDay) {


    List<Match> possibleMatches = matches.stream()
            .filter(match -> !alreadyScheduledTeamsInCurrentMatchDay.contains(match.getHomeTeam()) && !alreadyScheduledTeamsInCurrentMatchDay.contains(match.getAwayTeam()))
            .collect(Collectors.toList());

    List<Match> possibleMatchesWithExclusionOfHomeTeams = new ArrayList<>(possibleMatches);

    possibleMatchesWithExclusionOfHomeTeams.removeIf(match -> homeTeamsInPreviousMatchDay.contains(match.getHomeTeam()));

    if (possibleMatchesWithExclusionOfHomeTeams.size() != 0) {
        possibleMatches = new ArrayList<>(possibleMatchesWithExclusionOfHomeTeams);
    }

    int randomNumber = new Random().nextInt(possibleMatches.size());
    return possibleMatches.get(randomNumber);
}

Team and Match blueprints are as follows:

@Data
@NoArgsConstructor
@AllArgsConstructor
@Builder
class Team {
    String name;
}


@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
class Match {

    private Team homeTeam;
    private Team awayTeam;
}

The algorithm doesn't work. The

Exception in thread "main" java.lang.IllegalArgumentException: bound must be positive

is thrown - it means that for some matchday for some team there are 0 possible matches, which satisfy those rules listed at the beginning. I'm not sure, what am I missing here and how the schedule algorithm should look like to reflect the real one algorithm. In other words, why possibleMatches.size() ever happen to be 0 and what corrections should be done to make this algorithm work properly?

RBarryYoung
  • 55,398
  • 14
  • 96
  • 137
Schroedinger
  • 301
  • 6
  • 17
  • Does this answer your question? [IllegalArgumentException: Bound must be positive](https://stackoverflow.com/questions/32101688/illegalargumentexception-bound-must-be-positive) – Torben Nov 04 '19 at 17:28
  • @Torben No, I do know what causes this error (`nextInt()` method). The question is why `possibleMatches.size()` ever happen to be 0 and how to make the algorithm work properly – Schroedinger Nov 04 '19 at 17:53
  • This sounds like a job for your debugger, which will directly *show* you the problematic conditions. – Sneftel Nov 04 '19 at 18:08
  • 1
    `int gamesNumberPerMatchDay = teamsNumber / 2;` might be troublesome too if you have an odd number of teams – Norbert Nov 04 '19 at 18:09
  • @Sneftel I tried and didn't see what correction should be done – Schroedinger Nov 04 '19 at 18:12
  • @Norbert van Nobeln - I know, the teams number is always even, it's not the root of the problem at all. It';s listed in the prerequisites – Schroedinger Nov 04 '19 at 18:12
  • 1
    Does this answer your question? [Generating natural schedule for a sports league](https://stackoverflow.com/questions/5913616/generating-natural-schedule-for-a-sports-league) – Prune Nov 04 '19 at 19:42
  • You seem to use an open "find some open pairing" search. There are many postings on how to schedule a league with just these properties; I've filed a duplicate with two such examples. Make your schedule meet the requirements by construction, not by general search. Otherwise, you get just the problem you have here: you will make a partial schedule that leaves the last match or two with no acceptable alternatives. – Prune Nov 04 '19 at 19:45
  • If you're curious about just *how* your algorithm goes wrong, insert the simple print tracing that you neglected to post for us. You say "seems like" in your "analysis" -- it shouldn't "seem", you should have direct evidence to *know* where it goes wrong (at this level; other bugs aren't so easy to trace). See this lovely [debug](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) blog for help. – Prune Nov 04 '19 at 19:46
  • @Prune I got direct evidence, but I didn't write it directly - I assumed it's obvious to readers. I know how to debug. Also I've provided Minimal, Reproducible Example – Schroedinger Nov 04 '19 at 20:53
  • @Prune Otherwise, _you get just the problem you have here: you will make a partial schedule that leaves the last match or two with no acceptable alternatives_ That's actually, what I didn't know before and I thought that "find some open pairing" search is used in scheduling algorithm – Schroedinger Nov 04 '19 at 20:55
  • Open pairing is used only when there is a variety of specific restrictions. For a well-designed league such as yours, it's a straightforward rotation. See the referenced duplicate, or widen the search for sports scheduling. – Prune Nov 04 '19 at 21:23

0 Answers0