生成非重複對

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 ] 

我遇到的問題是選擇這些對分成相等大小（3在這種情況下）的輪（桶）。

首輪便成爲

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; 
} 

星期四 「絕招」 這裏是一個subList()結果使用Collections.rotate。這意味着輪換實際上反映在原始列表中，所以我們最終列出了包括凍結團隊的完整列​​表，這使得更容易循環。

這些配對首先與最後一個匹配，第二個與倒數第二個匹配，依此類推。

與此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; 
}