Сортировка двумерного массива матчей так, чтобы у каждой команды было одинаковое количество домашних и выездных матчей
Я пытаюсь создать соревнование «Швейцарская модель» Лиги чемпионов УЕФА 24 с участием 36 команд. Каждая команда будет соревноваться с 8 уникальными соперниками, всего будет проведено 144 матча. Я уже составил список матчей. Есть ли способ отсортировать все матчи так, чтобы у каждой команды было равное количество (в данном случае 4) домашних и выездных игр? Первая позиция в матче указывает на команду хозяев, а вторая позиция указывает на команду гостей.
Я попытался проверить, превышает ли общее количество домашних игр первой команды 4 матча (так как туров 8). Если это так, то она становится командой гостей. Однако результаты по-прежнему распределены неравномерно.
const matchups = [
[
"35",
"36"
],
[
"36",
"34"
],
[
"12",
"36"
],
[
"36",
"28"
],
[
"36",
"3"
],
[
"36",
"19"
],
[
"36",
"16"
],
[
"36",
"14"
],
[
"13",
"20"
],
[
"12",
"13"
],
[
"13",
"27"
],
[
"7",
"13"
],
[
"1",
"13"
],
[
"21",
"13"
],
[
"35",
"13"
],
[
"13",
"15"
],
[
"37",
"3"
],
[
"21",
"37"
],
[
"54",
"37"
],
[
"11",
"37"
],
[
"37",
"27"
],
[
"1",
"37"
],
[
"37",
"14"
],
[
"22",
"37"
],
[
"15",
"17"
],
[
"11",
"15"
],
[
"15",
"27"
],
[
"1",
"15"
],
[
"15",
"54"
],
[
"41",
"15"
],
[
"40",
"15"
],
[
"23",
"1"
],
[
"40",
"23"
],
[
"25",
"23"
],
[
"24",
"23"
],
[
"41",
"23"
],
[
"23",
"3"
],
[
"23",
"9"
],
[
"18",
"23"
],
[
"41",
"27"
],
[
"27",
"54"
],
[
"40",
"27"
],
[
"27",
"18"
],
[
"27",
"19"
],
[
"7",
"3"
],
[
"33",
"3"
],
[
"32",
"3"
],
[
"2",
"3"
],
[
"3",
"54"
],
[
"41",
"29"
],
[
"40",
"29"
],
[
"29",
"28"
],
[
"2",
"29"
],
[
"10",
"29"
],
[
"26",
"29"
],
[
"12",
"29"
],
[
"29",
"22"
],
[
"25",
"34"
],
[
"34",
"24"
],
[
"10",
"34"
],
[
"34",
"16"
],
[
"11",
"34"
],
[
"48",
"34"
],
[
"34",
"17"
],
[
"14",
"24"
],
[
"14",
"9"
],
[
"33",
"14"
],
[
"25",
"14"
],
[
"7",
"14"
],
[
"14",
"17"
],
[
"21",
"17"
],
[
"48",
"17"
],
[
"32",
"17"
],
[
"17",
"16"
],
[
"12",
"17"
],
[
"28",
"1"
],
[
"28",
"25"
],
[
"28",
"21"
],
[
"28",
"43"
],
[
"11",
"28"
],
[
"28",
"9"
],
[
"54",
"12"
],
[
"54",
"33"
],
[
"54",
"43"
],
[
"54",
"25"
],
[
"16",
"25"
],
[
"16",
"33"
],
[
"16",
"43"
],
[
"7",
"16"
],
[
"16",
"18"
],
[
"19",
"24"
],
[
"19",
"12"
],
[
"19",
"48"
],
[
"11",
"19"
],
[
"10",
"19"
],
[
"19",
"1"
],
[
"2",
"43"
],
[
"43",
"18"
],
[
"40",
"43"
],
[
"7",
"43"
],
[
"32",
"43"
],
[
"18",
"48"
],
[
"18",
"10"
],
[
"18",
"2"
],
[
"18",
"20"
],
[
"25",
"7"
],
[
"26",
"25"
],
[
"32",
"9"
],
[
"9",
"48"
],
[
"9",
"22"
],
[
"9",
"2"
],
[
"9",
"10"
],
[
"41",
"20"
],
[
"20",
"22"
],
[
"20",
"21"
],
[
"20",
"10"
],
[
"20",
"40"
],
[
"20",
"32"
],
[
"10",
"41"
],
[
"35",
"10"
],
[
"22",
"33"
],
[
"22",
"7"
],
[
"35",
"22"
],
[
"22",
"32"
],
[
"48",
"35"
],
[
"48",
"40"
],
[
"48",
"41"
],
[
"24",
"41"
],
[
"24",
"2"
],
[
"24",
"21"
],
[
"24",
"12"
],
[
"33",
"32"
],
[
"33",
"11"
],
[
"33",
"35"
],
[
"26",
"32"
],
[
"21",
"7"
],
[
"26",
"21"
],
[
"1",
"26"
],
[
"1",
"35"
],
[
"2",
"40"
],
[
"2",
"26"
],
[
"35",
"26"
],
[
"26",
"11"
],
[
"12",
"11"
]
]
const totalRounds = 8;
matchups.forEach((matchup) => {
matchup.sort((homeTeam, awayTeam) => {
const homeMatch = matchups.filter((m) => m[0] === homeTeam);
return homeMatch.length > (totalRounds / 2 ) ? 1 : -1;
});
});
const home = _.groupBy(matchups, m=> m[0])
const away = _.groupBy(matchups, m=> m[1])
console.info("home", home)
console.info("away", away)
console.info("combined",_.mergeWith(home,away, ((objValue,srcValue)=>{
if (Array.isArray(objValue)){
return objValue.concat(srcValue);
}
})))
Да, я хочу, чтобы у каждой команды было 4 домашних и 4 выездных матча. Я просто использовал цикл while, чтобы продолжать повторять попытки и перетасовывать совпадения, чтобы оно работало. Если у вас есть лучший подход, пожалуйста, ответьте. Это последняя информация: jsfiddle.net/bjn8td1w
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 2
Вот пример пула из 5 команд:
Рассмотрим таблицу матчей дома/в гостях для команд от A до E:
это означает, например, что команда А играет дома против команд Б и С и на выезде против команд D и E.
Я произвольно заполнил матрицу матчей дома/на выезде, но это соответствует вашему правилу: 2 игры дома и 2 игры на выезде для каждой команды (в этом примере пула из 5 команд).
Теперь, если вы добавите некоторую случайность между вашим массивом [Team 1, Team 2, ...] и массивом [Team A, Team B, ...], вы получите рандомизированный чемпионат с соответствующим количеством домашних и выездных игр.
Я могу добавить больше деталей, если это не кристально ясно.
Обновлено:
Я не уверен, должны ли все 9 команд каждого пула играть друг с другом только один раз, или каждая команда из 36 перечисленных должна играть против 8 случайных противников, избегая повторной встречи.
Новый формат Лиги чемпионов похож на турнир по швейцарской системе. Все 36 команд объединены в одну большую группу или лигу, однако это не круговой формат. Вместо того, чтобы сражаться друг с другом, каждой команде нужно сразиться только с восемью уникальными соперниками, проведя 4 домашних игры и 4 игры на выезде. Восьмерка лучших напрямую выходит в раунд плей-офф. Этот формат для меня совершенно новый.
Тогда у меня нет решения, которое бы работало каждый раз с соответствующей случайностью.
Решите это с помощью max-flow-min-cut.
Создайте сеть следующим образом:
Узлы: Источник, Поглотитель, 1 на команду, 1 на матч.
Дуги:
- source -> team_i, емкость 4, для каждой команды.
- team_i -> match_j, емкость 1, для каждого из 8 матчей, включающих команду team_i.
- match_j -> сток, емкость 1, для каждого совпадения.
Теперь найдите максимальный поток через эту сеть, используя max-flow-min-cut. Поскольку все мощности являются целыми числами, мы можем найти целочисленное решение (где все потоки являются целыми числами). Интерпретируйте переход от команды к матчу как сообщение о том, что в этом матче команда играет дома.
Если решение существует, оно соответствует максимальному потоку 144, 1 на совпадение, и алгоритм max-flow-min-cut его найдет.
Лучшее, что я вижу для ваших данных, — это 127, что намного меньше 144.
Просто хочу уточнить: у вас есть 4 пула по 9 команд? И вы хотите, чтобы у каждой команды каждого пула было по 4 домашних игры и 4 выездных игры?