Бесприбыльные повторяющиеся пары в равных ведрах размера

Question

У меня есть список пара, генерируемый из этого кода

int n = listTeam.size(); 
for (int i = 0; i < n; i++) { 
    for (int j = i + 1; j < n; j++) { 
     if (i != j) 
      listTeamPairs.add(new Team[] { listTeam.get(i), listTeam.get(j) }); 
     } 
    } 
} 

Это будет правильно генерировать эти пары, если есть 6 команд.

[0 1 , 0 2 , 0 3 , 0 4 , 0 5 , 1 2 , 1 3 , 1 4 , 1 5 , 2 3 , 2 4 , 2 5 , 3 4 , 3 5 , 4 5 ] 

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

Первый раунд станет

0-1, 2-3, 4-5 

Проблема возникает во втором туре

0-2, 1-3 <- swap order of these matches. 
This leaves only team 4-5 again. Which is not valid. 

код, который генерирует раундов без недействительных записей, но не полное ведро

private boolean generateRound(Team[] teamInRound, List<Team[]> roundTeams) { 
    Team team1 = teamInRound[0]; 
    Team team2 = teamInRound[1]; 
    Optional<Team[]> t = roundTeams.stream().filter(p -> p[0].getName().contentEquals(team1.getName()) || 
        p[1].getName().contentEquals(team2.getName()) || p[0].getName().contentEquals(team2.getName()) || 
        p[1].getName().contentEquals(team1.getName())).findAny(); 
      if (t.isPresent()) 
       return false; 
      roundTeams.add(teamInRound); 
      tmpTeamPairs.remove(teamInRound); 

      return true; 
} 

private void generateRounds(List<Team[]> teams) { 

    for (int i = 0; i < listTeam.size()/2;i++) { 
     System.out.println("Reamining pairs"); 
     tmpTeamPairs.stream().forEach(p -> System.out.println(p[0].getName() + " - " + p[1].getName())); 
     if (i == 0) { 
      teams.add(tmpTeamPairs.get(0)); 
      tmpTeamPairs.remove(0); 

      continue; 
     } 
     for (Team[] pair : tmpTeamPairs) { 
      boolean b = generateRound(pair, teams); 
      if (b) { 
       break; 
      } 
     } 
    }  
} 

Глядя на предложенный ответ, он, похоже, не генерирует нужные ведра.

scheduled team 0 against team 4 
scheduled team 2 against team 3 <----- 
scheduled team 5 against team 1 
Array order 
0 
2 <--- 
5 
4 
3 <--- 
1 
Lag 5 - Lag3 
Lag1 - Lag2 <----- 
Lag4 - Lag 6 
----------------------------------------------- 
scheduled team 0 against team 5 
scheduled team 1 against team 4 
scheduled team 2 against team 3 <---- 
Array order 
0 
1 
2 <--- 
5 
4 
3 <--- 
Lag 5 - Lag4 
Lag 6 - Lag3 
Lag1 - Lag2 <----- 

Answer 1

Вот очередная реализация круглого графика малиновка.

Он возвращает список ведер пар. Пары только что реализованы с помощью List, хотя вы можете создать собственный класс.

Каждое ведро - это Set, так как заказ в ведре не имеет значения, если известны парные команды.

Расписание само по себе является List, так как заказ имеет значение в расписании.

Этот метод является общим, поэтому вы можете поставить команды Integer или String, чтобы узнать, хорошо ли это работает или использовать полноценный класс Team.

public static <T> List<Set<List<T>>> roundRobin(List<T> teams) { 

    int numTeams = teams.size(); 

    // For a proper league, we only allow even number of teams. 
    if (numTeams % 2 != 0) { 
     throw new IllegalArgumentException("Number of teams not even " + numTeams); 
    } 

    List<Set<List<T>>> result = new ArrayList<>(numTeams - 1); 


    // Implement the round robin by rotating the right side of the list 
    // every time, then pairing opposite teams. Note that the first 
    // item is not part of the rotation. 
    for (int i = 0; i < numTeams - 1; i++) { 
     Collections.rotate(teams.subList(1,numTeams), 1); 
     Set<List<T>> bucket = new HashSet<>(); 
     for (int j = 0; j < numTeams/2; j++) { 
      bucket.add(Arrays.asList(teams.get(j), teams.get(numTeams - j - 1))); 
     } 
     result.add(bucket); 
    } 
    return result; 
} 

чт "трюк" здесь используется Collections.rotate на subList() результат. Это означает, что поворот фактически отражен в исходном списке, поэтому мы получаем полный список, включая замороженную команду, что упрощает цикл для пар.

Пары сопоставляются сначала с последним, вторым с предпоследним и так далее.

Запуск этого с этим main:

List<String> teams = Arrays.asList(
          "Manchester Utd.", 
          "Chelsea", 
          "Tottenham", 
          "Liverpool", 
          "Arsenal", 
          "West Ham Utd."); 

    for (Set<List<String>> bucket : roundRobin(teams)) { 
     for (List<String> pair : bucket) { 
      System.out.println(pair); 
     } 
     System.out.println(); 
    } 

Результаты в:

 
[West Ham Utd., Liverpool] 
[Chelsea, Tottenham] 
[Manchester Utd., Arsenal] 

[Manchester Utd., Liverpool] 
[Arsenal, Tottenham] 
[West Ham Utd., Chelsea] 

[Liverpool, Chelsea] 
[Manchester Utd., Tottenham] 
[Arsenal, West Ham Utd.] 

[Liverpool, Arsenal] 
[Tottenham, West Ham Utd.] 
[Manchester Utd., Chelsea] 

[Manchester Utd., West Ham Utd.] 
[Tottenham, Liverpool] 
[Chelsea, Arsenal] 

Обратите внимание, что в режиме реального спортивного сценария, график также отражает, кто играет в домашнем суде, а кто играет далеко. Здесь замороженная команда может играть все свои игры дома, по крайней мере, в первом раунде. Если вам нужно иметь изрядное планирование дома вдали, вы можете изменить строку:

bucket.add(Arrays.asList(teams.get(j), teams.get(numTeams - j - 1))); 

к:

Set<List<T>> pair = Arrays.asList(teams.get(j), teams.get(numTeams - j - 1)); 
if (i % 2 == 1 && j == 0) { 
    Collections.reverse(pair); 
} 
bucket.add(pair); 

Answer 2

Что вы хотите достичь - это составить турнирный план с раундами. Это можно сделать с помощью алгоритма планирования круглого цикла Round robin scheduling

Это работает, если зафиксировать одного из конкурентов, скажем 0. Остальное будет повернуто по часовой стрелке для создания новых комбинаций.

Код для достижения этой цели может выглядеть примерно так:

public static void generateRoundRobinPairs(List<Integer> teams) { 
    Integer fixedElement = teams.get(0); 
    List<Integer> teamsWithoutFirst = teams.subList(1,teams.size()); 
    for (int i = 0; i < teamsWithoutFirst.size(); i++) { 
     List<Integer> toSchedule = new ArrayList<>(); 
     toSchedule.add(fixedElement); 
     teamsWithoutFirst = buildNewRotation(teamsWithoutFirst); 
     toSchedule.addAll(teamsWithoutFirst); 
     scheduleRound(toSchedule); 
    } 
} 

public static void scheduleRound(List<Integer> teams) { 
    for (int i = 0; i < teams.size()/2; i++) { 
     // here create your data structure 
     String template ="scheduled team %s against team %s"; 
     System.out.println(String.format(template, teams.get(i), teams.get(i + teams.size()/2))); 
    } 
} 

public static List<Integer> buildNewRotation(List<Integer> l) { 
    List<Integer> newList = new ArrayList<>(); 
    newList.add(l.get(l.size()/2)); 

    for (int i = 0; i < l.size()/2 - 1; i++) { 
     newList.add(l.get(i)); 
    } 
    for (int i = 0; i < l.size()/2; i++) { 
     newList.add(l.get(i + 1 + l.size()/2)); 
    } 

    newList.add(l.get(l.size()/2 - 1)); 
    return newList; 
}