1

I can't come up with a solution and therefore I would like to ask for help. I have a list of names:

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

And I want by clicking a button to generate some random couplings between them, without repeating the already coupled name. Example:

John - James, William - George, Charles - Joseph, Frank - Henry, Robert - Edward, Thomas - Harry, Walter - Arthur

And after generating this list, I want to generate other lists for n times until all names are matched together. An example of what I want to do is on this site: https://www.blia.it/utili/campionato/ . By adding the names in the columns, it generates calendars with teams paired with each other and does not repeat the same pairing more than 2 times.

How can I do this in JavaScript and Java? Thanks to anyone who can help me.

Arvind Kumar Avinash
  • 71,965
  • 6
  • 74
  • 110
gianninho
  • 56
  • 6
  • 1
    Syntax looks like JavaScript not Java. So which one is it? "Either one" is not acceptable, I'm afraid. You'll have to choose. – Federico klez Culloca Dec 31 '20 at 12:24
  • 1
    Create a java set, add all your items in it after that get and remove items from it if you don't want them to repeat. Set is unordered you'll get randomized names while iterating and also takes care of uniqueness.. – Naruto26 Dec 31 '20 at 12:34
  • 2
    The first part of your question is answered here: https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n – Reto Höhener Dec 31 '20 at 12:37
  • @FedericoklezCulloca i wrote that i can do it in java or in javascript. Since I am doing both backend and frontend. :) – gianninho Dec 31 '20 at 13:04
  • @Naruto26 I tried to do this, but created the first group of pairs everything is ok. How can I then in the second group that I want to create not to repeat the same pair already existing in the first group? I hope I was clear. – gianninho Dec 31 '20 at 13:04
  • @RetoHöhener Thanks, I'll check the answers. – gianninho Dec 31 '20 at 13:04
  • Does this answer your question? [Algorithm to return all combinations of k elements from n](https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n) – Johannes Kuhn Jan 02 '21 at 15:53

2 Answers2

1

I don't understand the mathematics, but experimentation suggests that only 4, 8, 16, 32 teams etc. yield possible solutions.

Based on your comments, this edit allows consecutive home and away games. I didn't try specifically, but this attempt already seems to produce a pretty fair solution.

If you duplicate the solution for the second half of the season and switch every pairing, each team will get exactly the same amount of home and away games.

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

Output for 8 teams:

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
Reto Höhener
  • 5,419
  • 4
  • 39
  • 79
  • Hello thank you very much for the reply. The answer is almost correct, only that I would need the days randomly, if I click the button again, the combinations remain unchanged. I obviously need random. I tried to do Collections.shuffle(pairings), but in some cases it can't match the days correctly, except "couldn't find pairing" – gianninho Dec 31 '20 at 16:50
  • Obviously that is either your job to figure out or a separate question. – Reto Höhener Dec 31 '20 at 16:56
  • A hint: Shuffle the players list at the beginning. – Reto Höhener Dec 31 '20 at 17:01
  • Yes, I've already tried. But as you can see from your example, team number 1 will play 8 consecutive home games. For this I was trying to shuffle the pairings. – gianninho Dec 31 '20 at 18:40
  • 1
    @gianninho I made an attempt to satisfy the home/away requirement. Not sure if is correct, or the best possible solution. It seemed to produce a reasonable solution, so I stopped. – Reto Höhener Jan 02 '21 at 15:37
0

For generating pairings without repetition you could use a random index and pop the elements out of the array so they don't repeat.

For the second part of the question I would create an object with a key entry for each pairing made and I would check that the key doesn't exist after each draw.

Here is a blueprint of the problem. https://codesandbox.io/s/heuristic-grothendieck-vkt6f?file=/src/index.js

Dharman
  • 30,962
  • 25
  • 85
  • 135
eloyra
  • 519
  • 2
  • 6