我有一个列表，如何创建不重复n次的伙伴

gk7wooem  于 2021-06-29  发布在  Java
关注(0)|答案(2)|浏览(235)

关闭。这个问题需要更加突出重点。它目前不接受答案。
**想改进这个问题吗？**通过编辑这篇文章更新这个问题，使它只关注一个问题。

7天前关门了。
改进这个问题
我想不出解决办法，所以我想寻求帮助。我有一张名单：

var listNames = ['John', 'William', 'James', 'George', 'Charles',
                 'Frank', 'Joseph', 'Henry', 'Robert', 'Thomas',
                 'Edward', 'Harry', 'Walter', 'Arthur'];

我想通过点击一个按钮在它们之间生成一些随机耦合，而不重复已经耦合的名称。例子：
约翰-詹姆斯，威廉-乔治，查尔斯-约瑟夫，弗兰克-亨利，罗伯特-爱德华，托马斯-哈里，沃尔特-亚瑟
在生成这个列表之后，我想生成n次其他列表，直到所有的名字都匹配在一起。我想做的一个例子是在这个网站上：https://www.blia.it/utili/campionato/ . 通过在列中添加名称，它将生成团队相互配对的日历，并且不会重复相同的配对超过2次。
如何在javascript和java中实现这一点？谢谢任何能帮助我的人。

JavaJavaScriptreact-redux

2条答案

按热度按时间
e5nszbig

e5nszbig1#

为了生成不重复的配对，可以使用随机索引，将元素从数组中弹出，这样它们就不会重复。
对于问题的第二部分，我将为每个配对创建一个带有密钥条目的对象，并在每次绘制之后检查密钥是否不存在。
这是问题的蓝图。https://codesandbox.io/s/heuristic-grothendieck-vkt6f?file=/src/index.js

赞(0）分享  回复(0）举报  2021-06-29
db2dz4w8

db2dz4w82#

我不懂数学，但实验表明，只有4、8、16、32个团队等能给出可能的解决方案。
根据您的评论，此编辑允许连续主客场比赛。我没有具体尝试，但这种尝试似乎已经产生了一个相当公平的解决方案。
如果你在下半个赛季重复这个解决方案，并且切换每一个配对，每一支球队将会得到完全相同的主客场比赛数量。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Season {
  private static final int NUMBER_OF_TEAMS = 8 /* 4, 8, 16, 32, 64... */;

  private static class Day {
    private int           index    = -1;
    private List<Pairing> pairings = new ArrayList<>();

    @Override
    public String toString() {
      return String.format("Day %2d: %s", index + 1, pairings);
    }
  }

  private static class Pairing {
    private int a;
    private int b;

    @Override
    public String toString() {
      return String.format("%2d-%2d", a + 1, b + 1);
    }
  }

  public static void main(String[] args) throws Exception {
    List<Integer> teams = IntStream.range(0, NUMBER_OF_TEAMS).mapToObj(i -> Integer.valueOf(i)).collect(Collectors.toList());

    List<Pairing> pairings = createPairings(teams);
    System.out.println("all pairings: " + pairings);

    List<Day> days = createMatchDays(teams, pairings);

    System.out.println();
    System.out.println("match days first half of season (systematic):");
    days.forEach(i -> System.out.println(i));

    alternateHomeAndAwayGames(days);
  }

  private static List<Pairing> createPairings(List<Integer> teams) {
    // "n choose 2", or C(n,2)
    List<Pairing> pairings = new ArrayList<>();
    for(int a = 0; a < teams.size(); a++) {
      for(int b = a + 1; b < teams.size(); b++) {
        Pairing pairing = new Pairing();
        pairing.a = teams.get(a);
        pairing.b = teams.get(b);
        pairings.add(pairing);
      }
    }
    return pairings;
  }

  private static List<Day> createMatchDays(List<Integer> teams, List<Pairing> pairings) {
    int numberOfMatchDays = teams.size() - 1;
    int pairingsPerMatchDay = teams.size() / 2;
    List<Pairing> remainingPairings = new ArrayList<>(pairings);
    List<Day> days = new ArrayList<>();
    for(int dayIndex = 0; dayIndex < numberOfMatchDays; dayIndex++) {
      Day day = new Day();
      days.add(day);
      day.index = dayIndex;
      Set<Integer> teamsAlreadyPlaying = new HashSet<>();
      for(int i = 0; i < pairingsPerMatchDay; i++) {
        Pairing pairing = findPairing(remainingPairings, teamsAlreadyPlaying);
        day.pairings.add(pairing);
      }
    }
    return days;
  }

  private static Pairing findPairing(List<Pairing> remainingPairings, Set<Integer> teamsAlreadyPlaying) {
    for(Pairing candidate : remainingPairings) {
      if(!teamsAlreadyPlaying.contains(candidate.a) && !teamsAlreadyPlaying.contains(candidate.b)) {
        teamsAlreadyPlaying.add(candidate.a);
        teamsAlreadyPlaying.add(candidate.b);
        remainingPairings.remove(candidate);
        return candidate;
      }
    }

    throw new IllegalStateException("failed to find pairing");
  }

  private static void alternateHomeAndAwayGames(List<Day> days) {
    System.out.println();
    System.out.println("trying to alternate home and away games as much as possible...");
    int[] repeatHome = new int[NUMBER_OF_TEAMS];
    int[] repeatAway = new int[NUMBER_OF_TEAMS];

    for(int dayIndex = 1; dayIndex < days.size(); dayIndex++) {
      Day prevDay = days.get(dayIndex - 1);
      Day nextDay = days.get(dayIndex);
      System.out.println("fitting day " + (dayIndex + 1));

      // mark for each team if it played home or away during last day
      boolean[] playedHome = new boolean[NUMBER_OF_TEAMS];
      boolean[] playedAway = new boolean[NUMBER_OF_TEAMS];
      for(Pairing pairing : prevDay.pairings) {
        playedHome[pairing.a] = true;
        playedAway[pairing.b] = true;
      }

      // try to switch pairings of candidate, so that no team has to play home or away twice in a row
      for(int pairIndex = 0; pairIndex < nextDay.pairings.size(); pairIndex++) {
        Pairing pairing = nextDay.pairings.get(pairIndex);

        if(playedHome[pairing.a] && playedAway[pairing.b]) {
          switchTeamsInPairing(pairing);
        }

        if(!playedHome[pairing.a] && !playedAway[pairing.b]) {
          // ok
          playedHome[pairing.a] = true;
          playedAway[pairing.b] = true;
          continue;
        }

        // first try a-b
        if(pairing.a > pairing.b) {
          switchTeamsInPairing(pairing);
        }

        if(playedHome[pairing.a]) {
          repeatHome[pairing.a]++;
          System.out.println(String.format("%s  Pair %2d repeat team %2d: home+ %s away  %s", nextDay, pairIndex + 1, pairing.a + 1,
              repeatHome[pairing.a], repeatAway[pairing.a]));
          continue;
        }

        if(playedAway[pairing.b]) {
          repeatAway[pairing.b]++;
          System.out.println(String.format("%s  Pair %2d repeat team %2d: home  %s away+ %s", nextDay, pairIndex + 1, pairing.b + 1,
              repeatHome[pairing.b], repeatAway[pairing.b]));
          continue;
        }

        // then try b-a
        switchTeamsInPairing(pairing);

        if(playedHome[pairing.a]) {
          repeatHome[pairing.a]++;
          System.out.println(String.format("%s  Pair %2d repeat team %2d: home+ %s away  %s", nextDay, pairIndex + 1, pairing.a + 1,
              repeatHome[pairing.a], repeatAway[pairing.a]));
          continue;
        }

        if(playedAway[pairing.b]) {
          repeatAway[pairing.b]++;
          System.out.println(String.format("%s  Pair %2d repeat team %2d: home  %s away+ %s", nextDay, pairIndex + 1, pairing.b + 1,
              repeatHome[pairing.b], repeatAway[pairing.b]));
          continue;
        }
      }
    }

    System.out.println();
    System.out.println("match days first half of season (shuffled):");
    days.forEach(i -> System.out.println(i));

    // count home/away
    int[] home = new int[NUMBER_OF_TEAMS];
    int[] away = new int[NUMBER_OF_TEAMS];
    for(Day day : days) {
      for(Pairing pairing : day.pairings) {
        home[pairing.a]++;
        away[pairing.b]++;
      }
    }

    System.out.println("statistics");
    for(int i = 0; i < NUMBER_OF_TEAMS; i++) {
      System.out.println(String.format("Team %2d:  home/away: %2d/%2d  home/away-repeats: %2d/%2d", i + 1, home[i], away[i], repeatHome[i],
          repeatAway[i]));
    }

  }

  private static void switchTeamsInPairing(Pairing pairing) {
    int tmp = pairing.a;
    pairing.a = pairing.b;
    pairing.b = tmp;
  }
}

8组输出：

all pairings: [ 1- 2,  1- 3,  1- 4,  1- 5,  1- 6,  1- 7,  1- 8,  2- 3,  2- 4,  2- 5,  2- 6,  2- 7,  2- 8,  3- 4,  3- 5,  3- 6,  3- 7,  3- 8,  4- 5,  4- 6,  4- 7,  4- 8,  5- 6,  5- 7,  5- 8,  6- 7,  6- 8,  7- 8]

match days first half of season (systematic):
Day  1: [ 1- 2,  3- 4,  5- 6,  7- 8]
Day  2: [ 1- 3,  2- 4,  5- 7,  6- 8]
Day  3: [ 1- 4,  2- 3,  5- 8,  6- 7]
Day  4: [ 1- 5,  2- 6,  3- 7,  4- 8]
Day  5: [ 1- 6,  2- 5,  3- 8,  4- 7]
Day  6: [ 1- 7,  2- 8,  3- 5,  4- 6]
Day  7: [ 1- 8,  2- 7,  3- 6,  4- 5]

trying to alternate home and away games as much as possible...
fitting day 2
Day  2: [ 1- 3,  2- 4,  5- 7,  6- 8]  Pair  1 repeat team  1: home+ 1 away  0
Day  2: [ 1- 3,  2- 4,  5- 7,  6- 8]  Pair  2 repeat team  4: home  0 away+ 1
Day  2: [ 1- 3,  2- 4,  5- 7,  6- 8]  Pair  3 repeat team  5: home+ 1 away  0
Day  2: [ 1- 3,  2- 4,  5- 7,  6- 8]  Pair  4 repeat team  8: home  0 away+ 1
fitting day 3
fitting day 4
Day  4: [ 1- 5,  2- 6,  3- 7,  4- 8]  Pair  1 repeat team  5: home  1 away+ 1
Day  4: [ 1- 5,  2- 6,  3- 7,  4- 8]  Pair  2 repeat team  6: home  0 away+ 1
Day  4: [ 1- 5,  2- 6,  3- 7,  4- 8]  Pair  3 repeat team  3: home+ 1 away  0
Day  4: [ 1- 5,  2- 6,  3- 7,  4- 8]  Pair  4 repeat team  4: home+ 1 away  1
fitting day 5
fitting day 6
fitting day 7

match days first half of season (shuffled):
Day  1: [ 1- 2,  3- 4,  5- 6,  7- 8]
Day  2: [ 1- 3,  2- 4,  5- 7,  6- 8]
Day  3: [ 4- 1,  3- 2,  8- 5,  7- 6]
Day  4: [ 1- 5,  2- 6,  3- 7,  4- 8]
Day  5: [ 6- 1,  5- 2,  8- 3,  7- 4]
Day  6: [ 1- 7,  2- 8,  3- 5,  4- 6]
Day  7: [ 8- 1,  7- 2,  6- 3,  5- 4]
statistics
Team  1:  home/away:  4/ 3  home/away-repeats:  1/ 0
Team  2:  home/away:  3/ 4  home/away-repeats:  0/ 0
Team  3:  home/away:  4/ 3  home/away-repeats:  1/ 0
Team  4:  home/away:  3/ 4  home/away-repeats:  1/ 1
Team  5:  home/away:  4/ 3  home/away-repeats:  1/ 1
Team  6:  home/away:  3/ 4  home/away-repeats:  0/ 1
Team  7:  home/away:  4/ 3  home/away-repeats:  0/ 0
Team  8:  home/away:  3/ 4  home/away-repeats:  0/ 1
赞(0）分享  回复(0）举报  2021-06-29
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com