我已经将 36 支球队分配到 144 场比赛中,每场对阵 8 个对手。我想把比赛分成8轮,所以每轮有18场比赛,但限制是每支球队每轮只能比赛一次。这基本上是新的欧洲冠军联赛瑞士系统格式。我尝试了一个 while 循环来不断重试和洗牌比赛,但经过 100 次尝试后它仍然不起作用。有些回合的比赛数量少于或超过 18 场。你认为在不改变对局的情况下有可能吗?这是我的代码 [jsFiddle]:
const matchups = [
[
"26",
"10"
],
[
"26",
"23"
],
[
"26",
"7"
],
[
"28",
"26"
],
[
"21",
"26"
],
[
"32",
"26"
],
[
"36",
"26"
],
[
"26",
"22"
],
[
"43",
"25"
],
[
"25",
"54"
],
[
"25",
"11"
],
[
"37",
"25"
],
[
"16",
"25"
],
[
"27",
"25"
],
[
"25",
"20"
],
[
"25",
"2"
],
[
"14",
"36"
],
[
"37",
"36"
],
[
"36",
"43"
],
[
"36",
"15"
],
[
"11",
"36"
],
[
"29",
"36"
],
[
"36",
"41"
],
[
"23",
"3"
],
[
"23",
"24"
],
[
"23",
"43"
],
[
"27",
"23"
],
[
"10",
"23"
],
[
"29",
"23"
],
[
"23",
"37"
],
[
"54",
"13"
],
[
"48",
"54"
],
[
"54",
"40"
],
[
"54",
"41"
],
[
"54",
"18"
],
[
"34",
"54"
],
[
"12",
"54"
],
[
"2",
"29"
],
[
"2",
"12"
],
[
"24",
"2"
],
[
"2",
"13"
],
[
"7",
"2"
],
[
"20",
"2"
],
[
"2",
"21"
],
[
"7",
"43"
],
[
"1",
"43"
],
[
"43",
"15"
],
[
"43",
"41"
],
[
"43",
"28"
],
[
"48",
"37"
],
[
"7",
"37"
],
[
"22",
"37"
],
[
"37",
"11"
],
[
"37",
"24"
],
[
"1",
"27"
],
[
"11",
"1"
],
[
"1",
"12"
],
[
"14",
"1"
],
[
"1",
"21"
],
[
"9",
"1"
],
[
"29",
"1"
],
[
"35",
"16"
],
[
"35",
"20"
],
[
"10",
"35"
],
[
"28",
"35"
],
[
"35",
"19"
],
[
"11",
"35"
],
[
"22",
"35"
],
[
"35",
"48"
],
[
"15",
"33"
],
[
"17",
"15"
],
[
"15",
"40"
],
[
"15",
"10"
],
[
"12",
"15"
],
[
"15",
"9"
],
[
"33",
"11"
],
[
"9",
"11"
],
[
"11",
"34"
],
[
"27",
"19"
],
[
"48",
"27"
],
[
"34",
"27"
],
[
"13",
"27"
],
[
"27",
"33"
],
[
"9",
"48"
],
[
"9",
"17"
],
[
"28",
"9"
],
[
"20",
"9"
],
[
"14",
"9"
],
[
"17",
"14"
],
[
"28",
"17"
],
[
"17",
"48"
],
[
"17",
"20"
],
[
"16",
"17"
],
[
"22",
"17"
],
[
"19",
"3"
],
[
"19",
"40"
],
[
"13",
"19"
],
[
"19",
"22"
],
[
"19",
"29"
],
[
"33",
"19"
],
[
"32",
"21"
],
[
"10",
"32"
],
[
"18",
"32"
],
[
"32",
"28"
],
[
"16",
"32"
],
[
"32",
"3"
],
[
"20",
"32"
],
[
"22",
"28"
],
[
"13",
"22"
],
[
"10",
"22"
],
[
"41",
"14"
],
[
"41",
"7"
],
[
"41",
"29"
],
[
"41",
"34"
],
[
"16",
"41"
],
[
"3",
"16"
],
[
"3",
"28"
],
[
"3",
"10"
],
[
"3",
"7"
],
[
"24",
"3"
],
[
"18",
"16"
],
[
"13",
"16"
],
[
"18",
"7"
],
[
"7",
"14"
],
[
"33",
"29"
],
[
"29",
"34"
],
[
"21",
"13"
],
[
"21",
"33"
],
[
"21",
"12"
],
[
"24",
"21"
],
[
"20",
"48"
],
[
"48",
"10"
],
[
"40",
"14"
],
[
"24",
"40"
],
[
"40",
"12"
],
[
"40",
"18"
],
[
"40",
"34"
],
[
"12",
"18"
],
[
"12",
"20"
],
[
"34",
"13"
],
[
"34",
"18"
],
[
"14",
"24"
],
[
"18",
"33"
],
[
"33",
"24"
]
]
const totalRounds = 8
const matchesEachRound = 18;
let rounds: TeamId[][][] = [];
let trial = 0;
while (trial++ < 100) {
rounds = Array(totalRounds)
.fill([])
.map(() => []);
for (const matchup of _.shuffle(matchups)) {
let findTargetRound = rounds.find((round) => {
return (
(round.length < matchesEachRound &&
// both teams not complete in this round
_.intersection(round.flat(), matchup).length === 0)
);
});
if (findTargetRound) {
findTargetRound.push(matchup);
}
}
if (rounds.flat().length === matchups.length) {
break;
}
}
console.log(rounds)
解决方案如下。我通过将您的问题转换为图表发现了这一点,其中每场比赛都是一个节点,并且每对比赛如果兼容,就会获得一条边缘,这意味着所涉及的团队都不相同。
然后,我使用了一种称为“迭代贪婪”的概率派系查找技术来在此图中查找一组大小为 18 的派系。最后,我将其翻译回匹配组。
我没有计算它所花费的迭代次数,但这是一个很大的数字,即使不是数十亿,也有数亿。
首先,为了方便起见,我会给你的比赛编号:
0: match between 26 and 10, [26, 10]
1: match between 26 and 23, [26, 23]
2: match between 26 and 7, [26, 7]
3: match between 28 and 26, [28, 26]
4: match between 21 and 26, [21, 26]
5: match between 32 and 26, [32, 26]
6: match between 36 and 26, [36, 26]
7: match between 26 and 22, [26, 22]
8: match between 43 and 25, [43, 25]
9: match between 25 and 54, [25, 54]
10: match between 25 and 11, [25, 11]
11: match between 37 and 25, [37, 25]
12: match between 16 and 25, [16, 25]
13: match between 27 and 25, [27, 25]
14: match between 25 and 20, [25, 20]
15: match between 25 and 2, [25, 2]
16: match between 14 and 36, [14, 36]
17: match between 37 and 36, [37, 36]
18: match between 36 and 43, [36, 43]
19: match between 36 and 15, [36, 15]
20: match between 11 and 36, [11, 36]
21: match between 29 and 36, [29, 36]
22: match between 36 and 41, [36, 41]
23: match between 23 and 3, [23, 3]
24: match between 23 and 24, [23, 24]
25: match between 23 and 43, [23, 43]
26: match between 27 and 23, [27, 23]
27: match between 10 and 23, [10, 23]
28: match between 29 and 23, [29, 23]
29: match between 23 and 37, [23, 37]
30: match between 54 and 13, [54, 13]
31: match between 48 and 54, [48, 54]
32: match between 54 and 40, [54, 40]
33: match between 54 and 41, [54, 41]
34: match between 54 and 18, [54, 18]
35: match between 34 and 54, [34, 54]
36: match between 12 and 54, [12, 54]
37: match between 2 and 29, [2, 29]
38: match between 2 and 12, [2, 12]
39: match between 24 and 2, [24, 2]
40: match between 2 and 13, [2, 13]
41: match between 7 and 2, [7, 2]
42: match between 20 and 2, [20, 2]
43: match between 2 and 21, [2, 21]
44: match between 7 and 43, [7, 43]
45: match between 1 and 43, [1, 43]
46: match between 43 and 15, [43, 15]
47: match between 43 and 41, [43, 41]
48: match between 43 and 28, [43, 28]
49: match between 48 and 37, [48, 37]
50: match between 7 and 37, [7, 37]
51: match between 22 and 37, [22, 37]
52: match between 37 and 11, [37, 11]
53: match between 37 and 24, [37, 24]
54: match between 1 and 27, [1, 27]
55: match between 11 and 1, [11, 1]
56: match between 1 and 12, [1, 12]
57: match between 14 and 1, [14, 1]
58: match between 1 and 21, [1, 21]
59: match between 9 and 1, [9, 1]
60: match between 29 and 1, [29, 1]
61: match between 35 and 16, [35, 16]
62: match between 35 and 20, [35, 20]
63: match between 10 and 35, [10, 35]
64: match between 28 and 35, [28, 35]
65: match between 35 and 19, [35, 19]
66: match between 11 and 35, [11, 35]
67: match between 22 and 35, [22, 35]
68: match between 35 and 48, [35, 48]
69: match between 15 and 33, [15, 33]
70: match between 17 and 15, [17, 15]
71: match between 15 and 40, [15, 40]
72: match between 15 and 10, [15, 10]
73: match between 12 and 15, [12, 15]
74: match between 15 and 9, [15, 9]
75: match between 33 and 11, [33, 11]
76: match between 9 and 11, [9, 11]
77: match between 11 and 34, [11, 34]
78: match between 27 and 19, [27, 19]
79: match between 48 and 27, [48, 27]
80: match between 34 and 27, [34, 27]
81: match between 13 and 27, [13, 27]
82: match between 27 and 33, [27, 33]
83: match between 9 and 48, [9, 48]
84: match between 9 and 17, [9, 17]
85: match between 28 and 9, [28, 9]
86: match between 20 and 9, [20, 9]
87: match between 14 and 9, [14, 9]
88: match between 17 and 14, [17, 14]
89: match between 28 and 17, [28, 17]
90: match between 17 and 48, [17, 48]
91: match between 17 and 20, [17, 20]
92: match between 16 and 17, [16, 17]
93: match between 22 and 17, [22, 17]
94: match between 19 and 3, [19, 3]
95: match between 19 and 40, [19, 40]
96: match between 13 and 19, [13, 19]
97: match between 19 and 22, [19, 22]
98: match between 19 and 29, [19, 29]
99: match between 33 and 19, [33, 19]
100: match between 32 and 21, [32, 21]
101: match between 10 and 32, [10, 32]
102: match between 18 and 32, [18, 32]
103: match between 32 and 28, [32, 28]
104: match between 16 and 32, [16, 32]
105: match between 32 and 3, [32, 3]
106: match between 20 and 32, [20, 32]
107: match between 22 and 28, [22, 28]
108: match between 13 and 22, [13, 22]
109: match between 10 and 22, [10, 22]
110: match between 41 and 14, [41, 14]
111: match between 41 and 7, [41, 7]
112: match between 41 and 29, [41, 29]
113: match between 41 and 34, [41, 34]
114: match between 16 and 41, [16, 41]
115: match between 3 and 16, [3, 16]
116: match between 3 and 28, [3, 28]
117: match between 3 and 10, [3, 10]
118: match between 3 and 7, [3, 7]
119: match between 24 and 3, [24, 3]
120: match between 18 and 16, [18, 16]
121: match between 13 and 16, [13, 16]
122: match between 18 and 7, [18, 7]
123: match between 7 and 14, [7, 14]
124: match between 33 and 29, [33, 29]
125: match between 29 and 34, [29, 34]
126: match between 21 and 13, [21, 13]
127: match between 21 and 33, [21, 33]
128: match between 21 and 12, [21, 12]
129: match between 24 and 21, [24, 21]
130: match between 20 and 48, [20, 48]
131: match between 48 and 10, [48, 10]
132: match between 40 and 14, [40, 14]
133: match between 24 and 40, [24, 40]
134: match between 40 and 12, [40, 12]
135: match between 40 and 18, [40, 18]
136: match between 40 and 34, [40, 34]
137: match between 12 and 18, [12, 18]
138: match between 12 and 20, [12, 20]
139: match between 34 and 13, [34, 13]
140: match between 34 and 18, [34, 18]
141: match between 14 and 24, [14, 24]
142: match between 18 and 33, [18, 33]
143: match between 33 and 24, [33, 24]
第 1 组:
4: match between 21 and 26, [21, 26]
11: match between 37 and 25, [37, 25]
20: match between 11 and 36, [11, 36]
25: match between 23 and 43, [23, 43]
33: match between 54 and 41, [54, 41]
37: match between 2 and 29, [2, 29]
56: match between 1 and 12, [1, 12]
64: match between 28 and 35, [28, 35]
69: match between 15 and 33, [15, 33]
78: match between 27 and 19, [27, 19]
84: match between 9 and 17, [9, 17]
105: match between 32 and 3, [32, 3]
109: match between 10 and 22, [10, 22]
120: match between 18 and 16, [18, 16]
123: match between 7 and 14, [7, 14]
130: match between 20 and 48, [20, 48]
133: match between 24 and 40, [24, 40]
139: match between 34 and 13, [34, 13]
第2组
2: match between 26 and 7, [26, 7]
10: match between 25 and 11, [25, 11]
16: match between 14 and 36, [14, 36]
24: match between 23 and 24, [23, 24]
32: match between 54 and 40, [54, 40]
42: match between 20 and 2, [20, 2]
48: match between 43 and 28, [43, 28]
49: match between 48 and 37, [48, 37]
54: match between 1 and 27, [1, 27]
63: match between 10 and 35, [10, 35]
74: match between 15 and 9, [15, 9]
93: match between 22 and 17, [22, 17]
94: match between 19 and 3, [19, 3]
102: match between 18 and 32, [18, 32]
113: match between 41 and 34, [41, 34]
121: match between 13 and 16, [13, 16]
124: match between 33 and 29, [33, 29]
128: match between 21 and 12, [21, 12]
第 3 组:
7: match between 26 and 22, [26, 22]
8: match between 43 and 25, [43, 25]
17: match between 37 and 36, [37, 36]
28: match between 29 and 23, [29, 23]
30: match between 54 and 13, [54, 13]
39: match between 24 and 2, [24, 2]
55: match between 11 and 1, [11, 1]
65: match between 35 and 19, [35, 19]
71: match between 15 and 40, [15, 40]
79: match between 48 and 27, [48, 27]
87: match between 14 and 9, [14, 9]
92: match between 16 and 17, [16, 17]
103: match between 32 and 28, [32, 28]
111: match between 41 and 7, [41, 7]
117: match between 3 and 10, [3, 10]
127: match between 21 and 33, [21, 33]
138: match between 12 and 20, [12, 20]
140: match between 34 and 18, [34, 18]
第 4 组:
1: match between 26 and 23, [26, 23]
9: match between 25 and 54, [25, 54]
22: match between 36 and 41, [36, 41]
43: match between 2 and 21, [2, 21]
44: match between 7 and 43, [7, 43]
51: match between 22 and 37, [22, 37]
60: match between 29 and 1, [29, 1]
66: match between 11 and 35, [11, 35]
73: match between 12 and 15, [12, 15]
80: match between 34 and 27, [34, 27]
85: match between 28 and 9, [28, 9]
88: match between 17 and 14, [17, 14]
96: match between 13 and 19, [13, 19]
106: match between 20 and 32, [20, 32]
115: match between 3 and 16, [3, 16]
131: match between 48 and 10, [48, 10]
135: match between 40 and 18, [40, 18]
143: match between 33 and 24, [33, 24]
第 5 组:
3: match between 28 and 26, [28, 26]
15: match between 25 and 2, [25, 2]
21: match between 29 and 36, [29, 36]
29: match between 23 and 37, [23, 37]
34: match between 54 and 18, [54, 18]
45: match between 1 and 43, [1, 43]
67: match between 22 and 35, [22, 35]
72: match between 15 and 10, [15, 10]
77: match between 11 and 34, [11, 34]
81: match between 13 and 27, [13, 27]
83: match between 9 and 48, [9, 48]
91: match between 17 and 20, [17, 20]
99: match between 33 and 19, [33, 19]
104: match between 16 and 32, [16, 32]
110: match between 41 and 14, [41, 14]
118: match between 3 and 7, [3, 7]
129: match between 24 and 21, [24, 21]
134: match between 40 and 12, [40, 12]
第 6 组:
5: match between 32 and 26, [32, 26]
13: match between 27 and 25, [27, 25]
18: match between 36 and 43, [36, 43]
27: match between 10 and 23, [10, 23]
35: match between 34 and 54, [34, 54]
41: match between 7 and 2, [7, 2]
53: match between 37 and 24, [37, 24]
58: match between 1 and 21, [1, 21]
68: match between 35 and 48, [35, 48]
70: match between 17 and 15, [17, 15]
75: match between 33 and 11, [33, 11]
86: match between 20 and 9, [20, 9]
98: match between 19 and 29, [19, 29]
108: match between 13 and 22, [13, 22]
114: match between 16 and 41, [16, 41]
116: match between 3 and 28, [3, 28]
132: match between 40 and 14, [40, 14]
137: match between 12 and 18, [12, 18]
第 7 组:
0: match between 26 and 10, [26, 10]
12: match between 16 and 25, [16, 25]
19: match between 36 and 15, [36, 15]
23: match between 23 and 3, [23, 3]
36: match between 12 and 54, [12, 54]
40: match between 2 and 13, [2, 13]
47: match between 43 and 41, [43, 41]
52: match between 37 and 11, [37, 11]
59: match between 9 and 1, [9, 1]
62: match between 35 and 20, [35, 20]
82: match between 27 and 33, [27, 33]
90: match between 17 and 48, [17, 48]
95: match between 19 and 40, [19, 40]
100: match between 32 and 21, [32, 21]
107: match between 22 and 28, [22, 28]
122: match between 18 and 7, [18, 7]
125: match between 29 and 34, [29, 34]
141: match between 14 and 24, [14, 24]
第 8 组:
6: match between 36 and 26, [36, 26]
14: match between 25 and 20, [25, 20]
26: match between 27 and 23, [27, 23]
31: match between 48 and 54, [48, 54]
38: match between 2 and 12, [2, 12]
46: match between 43 and 15, [43, 15]
50: match between 7 and 37, [7, 37]
57: match between 14 and 1, [14, 1]
61: match between 35 and 16, [35, 16]
76: match between 9 and 11, [9, 11]
89: match between 28 and 17, [28, 17]
97: match between 19 and 22, [19, 22]
101: match between 10 and 32, [10, 32]
112: match between 41 and 29, [41, 29]
119: match between 24 and 3, [24, 3]
126: match between 21 and 13, [21, 13]
136: match between 40 and 34, [40, 34]
142: match between 18 and 33, [18, 33]