Coverage for moptipyapps / ttp / game_encoding.py: 49%
67 statements
« prev ^ index » next coverage.py v7.13.0, created at 2025-12-11 04:40 +0000
1"""
2A permutation-with-repetition-based encoding based on games.
4A point in the search space is a permutation (potentially with repetitions)
5that can be translated to a :class:`~moptipyapps.ttp.game_plan.GamePlan`.
6Each value `v` in the permutation represents a game to be played by two of
7the `n` teams. There are `n(n-1)` possible games between `n` teams,
8distinguishing home and away teams. Given a value `v` from `0..n(n-1)-1`,
9we can get the zero-based index of the home team as
10`home_idx = (game // (n - 1)) % n`. The away index is computed in two steps,
11first we set `away_idx = game % (n - 1)` and if `away_idx >= home_idx`, we
12do `away_idx = away_idx + 1`. (Because a team can never play against itself,
13the situation that `home_idx == away_idx` does not need to be represented, so
14we can "skip" over this possible value by doing the `away_idx = away_idy + 1`
15and thus get a more "compact" numeric range for the permutation elements.)
17A game schedule for any round-robin tournament with any given number of rounds
18can then be represented as permutation (potentially with repetitions) of these
19game values. In the decoding procedure, it is processed from beginning to end
20each game is then placed into the earliest slot not already occupied by
21another game. In other words, it is placed at the earliest day at which both
22involved teams do not yet have other games. If no such slot is available, this
23game is not placed at all. In this case, there will be some zeros in the game
24plan after the encoding. No other constraint is considered at this stage.
26In other words, this encoding may produce game plans that violate constraints.
27It does not care about the streak length constraints.
28It does not ensure that each team always has a game.
29Therefore, it should only be used in conjunction with objective functions that
30force the search towards feasible solutions, such as the
31:mod:`~moptipyapps.ttp.errors` objective.
33In :mod:`~moptipyapps.ttp.game_encoding_2`, we present a modified version of
34this encoding procedure that tries to reduce the number of zeros, i.e.,
35"byes," in the resulting schedule.
36"""
39from typing import Final
41import numba # type: ignore
42import numpy as np
43from moptipy.api.encoding import Encoding
44from moptipy.spaces.permutations import Permutations
45from pycommons.types import check_int_range
47from moptipyapps.ttp.instance import Instance
50@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
51def game_to_id(home: int | np.ndarray, away: int | np.ndarray, n: int) -> int:
52 """
53 Encode a game to a game ID.
55 :param home: the home team
56 :param away: the away team
57 :param n: the total number of teams
58 :return: the game ID
60 >>> game_to_id(0, 1, 2)
61 0
62 >>> game_to_id(1, 0, 2)
63 1
65 >>> game_to_id(0, 1, 4)
66 0
67 >>> game_to_id(0, 2, 4)
68 1
69 >>> game_to_id(0, 3, 4)
70 2
71 >>> game_to_id(1, 0, 4)
72 3
73 >>> game_to_id(1, 2, 4)
74 4
75 >>> game_to_id(1, 3, 4)
76 5
77 >>> game_to_id(2, 0, 4)
78 6
79 >>> game_to_id(2, 1, 4)
80 7
81 >>> game_to_id(2, 3, 4)
82 8
83 >>> game_to_id(3, 0, 4)
84 9
85 >>> game_to_id(3, 1, 4)
86 10
87 >>> game_to_id(3, 2, 4)
88 11
89 >>> game_to_id(5, 4, 10)
90 49
91 """
92 a = int(home)
93 b = int(away)
94 if b > a:
95 b -= 1
96 return (a * (n - 1)) + b
99def search_space_for_n_and_rounds(n: int, rounds: int) -> Permutations:
100 """
101 Create a proper search space for the given number of teams and rounds.
103 If the instance prescribes a double-round robin tournament, then this
104 is just the :meth:`~moptipy.spaces.permutations.Permutations.standard`
105 permutations set. Otherwise, it will be a permutation where some
106 elements are omitted (for
107 :attr:`~moptipyapps.ttp.instance.Instance.rounds` == 1) or duplicated
108 (if :attr:`~moptipyapps.ttp.instance.Instance.rounds` > 2).
110 If an odd number of rounds is played, then it is not possible that all
111 teams have the same number of games at home and away. Then, the
112 permutation is generated such that, if the highest numbers of games at
113 home for any team is `k`, no other team has less than `k - 1` games at
114 home. If the number of rounds is even, then all teams will have the
115 same number of home and away games, that is, the number of teams
116 divided by two and multiplied by the number of rounds.
118 :param n: the number of teams
119 :param rounds: the number of rounds
120 :return: the search space
122 >>> ",".join(map(str, search_space_for_n_and_rounds(2, 2).blueprint))
123 '0,1'
124 >>> ",".join(map(str, search_space_for_n_and_rounds(2, 3).blueprint))
125 '0,1,1'
126 >>> ",".join(map(str, search_space_for_n_and_rounds(2, 4).blueprint))
127 '0,0,1,1'
128 >>> ",".join(map(str, search_space_for_n_and_rounds(2, 5).blueprint))
129 '0,0,1,1,1'
130 >>> ",".join(map(str, search_space_for_n_and_rounds(3, 1).blueprint))
131 '1,2,5'
132 >>> ",".join(map(str, search_space_for_n_and_rounds(3, 2).blueprint))
133 '0,1,2,3,4,5'
134 >>> ",".join(map(str, search_space_for_n_and_rounds(3, 3).blueprint))
135 '0,1,1,2,2,3,4,5,5'
136 >>> ",".join(map(str, search_space_for_n_and_rounds(4, 1).blueprint))
137 '1,2,3,7,8,10'
138 >>> ",".join(map(str, search_space_for_n_and_rounds(4, 2).blueprint))
139 '0,1,2,3,4,5,6,7,8,9,10,11'
140 >>> ",".join(map(str, search_space_for_n_and_rounds(4, 3).blueprint))
141 '0,1,1,2,2,3,3,4,5,6,7,7,8,8,9,10,10,11'
142 >>> ",".join(map(str, search_space_for_n_and_rounds(4, 4).blueprint))
143 '0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11'
144 >>> ",".join(map(str, search_space_for_n_and_rounds(4, 5).blueprint))
145 '0,0,1,1,1,2,2,2,3,3,3,4,4,5,5,6,6,7,7,7,8,8,8,9,9,10,10,10,11,11'
146 >>> ",".join(map(str, search_space_for_n_and_rounds(5, 1).blueprint))
147 '1,2,4,7,9,10,13,15,16,18'
148 >>> ",".join(map(str, search_space_for_n_and_rounds(5, 2).blueprint))
149 '0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19'
150 >>> ",".join(map(str, search_space_for_n_and_rounds(5, 3).blueprint))
151 '0,1,1,2,2,3,4,4,5,6,7,7,8,9,9,10,10,11,12,13,13,14,15,15,16,16,17,18,\
15218,19'
153 """
154 check_int_range(n, "n", 2, 100000)
155 check_int_range(n, "rounds", 1, 100000)
156 games: Final[list[int]] = []
157 order: bool = False
158 for r in range(rounds):
159 # If we have an odd round of games, the very last round needs
160 # to be treated differently to ensure that the home-away games
161 # distribution is fair.
162 normal: bool = (r < (rounds - 1)) or ((rounds % 2) == 0)
163 for i in range(n): # for each city
164 for j in range(i): # for each other city
165 order = ((r % 2) == 0) if normal else (not order)
166 games.append(game_to_id(
167 i if order else j, j if order else i, n))
168 games.sort()
169 return Permutations(games) # create permutations with repetition
172@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
173def re_encode(x: np.ndarray, y: np.ndarray) -> None:
174 """
175 Re-encode a game plan to a permutation.
177 `x` must be a valid permutation. It is then transformed based on the game
178 plan `y` to represent `y` in a straightforward manner. The general
179 contract of this function is that:
181 - `y` can be a game plan of any kind, with all sorts of game scheduling
182 error except one: If team A plays team B in one slot, then team B must
183 also play against team A in that slot and exactly one of them is the
184 home team and one of them is the away team. Apart from that, there can
185 be arbitrary byes or streak violations.
186 - `x` must a valid game permutation, but can be entirely unrelated
187 to `y`.
188 - This function will then transform `x` such that `map_games(x, z)` will
189 result in a game plan such that `z = y`.
191 Due to the possibility of byes, it can happen that after
192 `map_games(x1, z)` and `re_encode(x2, z)` it may be that `x1 != x2`.
193 The reason is that the order of game IDs n `x2` for games that were not
194 scheduled in `z` will be undefined.
196 :param x: the permutation
197 :param y: the game plan
199 >>> from moptipyapps.ttp.instance import Instance
200 >>> inst = Instance.from_resource("con14")
201 >>> perm = np.array([70,114,54,51,98,31,49,46,148,169,174,151,155,110,
202 ... 75,118,128,81,171,19,133,93,5,91,47,1,84,109,142,121,7,40,163,
203 ... 61,20,96,165,177,160,39,73,37,101,108,119,65,2,117,164,106,60,
204 ... 145,105,90,170,74,8,26,94,10,22,86,120,154,89,66,77,178,140,48,
205 ... 0,52,159,25,176,135,63,57,76,161,68,124,162,29,55,80,24,45,85,
206 ... 115,131,100,17,53,27,38,95,158,104,175,87,123,167,97,79,112,172,
207 ... 127,136,12,44,50,102,69,144,143,113,4,181,88,166,150,59,141,72,
208 ... 125,116,132,14,147,153,129,111,92,62,6,32,82,16,179,21,3,126,
209 ... 134,122,149,146,36,107,34,103,42,41,18,35,78,28,137,43,33,71,99,
210 ... 139,56,23,138,67,168,130,30,180,152,83,9,13,173,11,157,156,64,
211 ... 15,58])
212 >>> teams = 14
213 >>> rounds = 2
214 >>> from moptipy.utils.nputils import int_range_to_dtype
215 >>> dest = np.empty((rounds * (teams - 1), teams),
216 ... int_range_to_dtype(-teams, teams))
217 >>> map_games(perm, dest)
218 >>> print(dest)
219 [[ -8 -10 -5 14 3 7 -6 1 12 2 -13 -9 11 -4]
220 [-14 -6 7 12 11 2 -3 9 -8 13 -5 -4 -10 1]
221 [ 7 8 -14 9 -10 -12 -1 -2 -4 5 13 6 -11 3]
222 [ -5 11 -8 -7 1 -14 4 3 -12 -13 -2 9 10 6]
223 [ 3 -5 -1 -11 2 10 -9 -13 7 -6 4 14 8 -12]
224 [ 9 -3 2 10 -13 12 8 -7 -1 -4 14 -6 5 -11]
225 [-10 -4 13 2 -11 -9 14 12 6 1 5 -8 -3 -7]
226 [ -4 9 -10 1 7 -8 -5 6 -2 3 -14 13 -12 11]
227 [ -6 -11 -12 -8 10 1 13 4 -14 -5 2 3 -7 9]
228 [ 4 -14 -13 -1 -9 11 10 -12 5 -7 -6 8 3 2]
229 [ 10 -7 5 8 -3 14 2 -4 -13 -1 12 -11 9 -6]
230 [ 12 14 -9 -10 13 -11 -8 7 3 4 6 -1 -5 -2]
231 [ -3 -9 1 11 -8 13 12 5 2 -14 -4 -7 -6 10]
232 [ 2 -1 -7 -13 -6 5 3 -14 10 -9 -12 11 4 8]
233 [-11 -12 14 -5 4 -13 9 -10 -7 8 1 2 6 -3]
234 [ -9 3 -2 -6 -14 4 -13 11 1 12 -8 -10 7 5]
235 [-12 13 8 5 -4 -10 -14 -3 11 6 -9 1 -2 7]
236 [ 8 6 10 -14 -12 -2 11 -1 13 -3 -7 5 -9 4]
237 [ 14 -8 -11 6 9 -4 -10 2 -5 7 3 -13 12 -1]
238 [ 6 0 0 13 12 -1 -11 14 -10 9 7 -5 -4 -8]
239 [ 11 5 12 7 -2 9 -4 13 -6 14 -1 -3 -8 -10]
240 [ 0 10 11 -12 -7 0 5 -9 8 -2 -3 4 -14 13]
241 [ 5 -13 -4 3 -1 8 -12 -6 14 11 -10 7 2 -9]
242 [ 0 7 0 -9 6 -5 -2 -11 4 -12 8 10 14 -13]
243 [ -7 12 4 -3 14 0 1 10 -11 -8 9 -2 0 -5]
244 [ -2 1 9 0 8 -7 6 -5 -3 -11 10 -14 0 12]]
245 >>> from moptipyapps.ttp.game_encoding_2 import map_games_2
246 >>> dest.fill(0)
247 >>> map_games_2(perm, dest)
248 >>> print(dest)
249 [[ -8 -10 -5 14 3 7 -6 1 12 2 -13 -9 11 -4]
250 [-14 -6 7 12 11 2 -3 9 -8 13 -5 -4 -10 1]
251 [ 7 8 -14 9 -10 -12 -1 -2 -4 5 13 6 -11 3]
252 [ -5 11 -8 -7 1 -14 4 3 -12 -13 -2 9 10 6]
253 [ 3 -5 -1 -11 2 10 -9 -13 7 -6 4 14 8 -12]
254 [ 9 -3 2 10 -13 12 8 -7 -1 -4 14 -6 5 -11]
255 [-10 -4 13 2 -11 -9 14 12 6 1 5 -8 -3 -7]
256 [ -4 9 -10 1 7 -8 -5 6 -2 3 -14 13 -12 11]
257 [ -6 -11 -12 -8 10 1 13 4 -14 -5 2 3 -7 9]
258 [ 4 -14 -13 -1 -9 11 10 -12 5 -7 -6 8 3 2]
259 [ 10 -7 5 8 -3 14 2 -4 -13 -1 12 -11 9 -6]
260 [ 12 14 -9 -10 13 -11 -8 7 3 4 6 -1 -5 -2]
261 [ -3 -9 1 11 -8 13 12 5 2 -14 -4 -7 -6 10]
262 [ 2 -1 -7 -13 -6 5 3 -14 10 -9 -12 11 4 8]
263 [-11 -12 14 -5 4 -13 9 -10 -7 8 1 2 6 -3]
264 [ -9 3 -2 -6 -14 4 -13 11 1 12 -8 -10 7 5]
265 [-12 13 8 5 -4 -10 -14 -3 11 6 -9 1 -2 7]
266 [ 8 6 10 -14 -12 -2 11 -1 13 -3 -7 5 -9 4]
267 [ 14 -8 -11 6 9 -4 -10 2 -5 7 3 -13 12 -1]
268 [ -2 1 -6 13 12 3 -11 14 -10 9 7 -5 -4 -8]
269 [ 11 5 12 7 -2 9 -4 13 -6 14 -1 -3 -8 -10]
270 [ 6 10 11 -12 -7 -1 5 -9 8 -2 -3 4 -14 13]
271 [ 5 -13 -4 3 -1 8 -12 -6 14 11 -10 7 2 -9]
272 [-13 7 6 -9 14 -3 -2 -11 4 -12 8 10 1 -5]
273 [ -7 12 4 -3 6 -5 1 10 -11 -8 9 -2 14 -13]
274 [ 13 4 9 -2 8 -7 6 -5 -3 -11 10 -14 -1 12]]
275 >>> re_encode(perm, dest)
276 >>> print(perm)
277 [ 51 54 70 91 114 118 166 31 49 61 66 98 128 169 5 19 46 121
278 141 148 171 22 52 81 93 151 165 174 1 53 73 110 133 155 163 7
279 27 47 75 84 142 160 37 40 90 101 109 117 134 20 39 57 96 119
280 154 179 60 65 89 94 131 145 177 2 74 86 108 150 158 170 8 29
281 45 77 79 140 164 10 25 63 97 106 120 135 26 48 76 88 95 105
282 178 0 69 80 112 153 159 176 38 55 85 124 130 144 161 14 68 100
283 104 127 162 173 24 32 42 113 122 143 175 6 17 34 87 115 147 172
284 12 43 59 92 123 132 167 13 50 62 67 103 125 136 9 16 36 44
285 72 102 129 4 21 35 82 111 146 181 3 41 71 116 126 149 157 18
286 30 64 107 137 152 156 23 28 56 78 99 138 168 11 15 33 58 83
287 139 180]
288 >>> dest.fill(0)
289 >>> map_games(perm, dest)
290 >>> print(dest)
291 [[ -8 -10 -5 14 3 7 -6 1 12 2 -13 -9 11 -4]
292 [-14 -6 7 12 11 2 -3 9 -8 13 -5 -4 -10 1]
293 [ 7 8 -14 9 -10 -12 -1 -2 -4 5 13 6 -11 3]
294 [ -5 11 -8 -7 1 -14 4 3 -12 -13 -2 9 10 6]
295 [ 3 -5 -1 -11 2 10 -9 -13 7 -6 4 14 8 -12]
296 [ 9 -3 2 10 -13 12 8 -7 -1 -4 14 -6 5 -11]
297 [-10 -4 13 2 -11 -9 14 12 6 1 5 -8 -3 -7]
298 [ -4 9 -10 1 7 -8 -5 6 -2 3 -14 13 -12 11]
299 [ -6 -11 -12 -8 10 1 13 4 -14 -5 2 3 -7 9]
300 [ 4 -14 -13 -1 -9 11 10 -12 5 -7 -6 8 3 2]
301 [ 10 -7 5 8 -3 14 2 -4 -13 -1 12 -11 9 -6]
302 [ 12 14 -9 -10 13 -11 -8 7 3 4 6 -1 -5 -2]
303 [ -3 -9 1 11 -8 13 12 5 2 -14 -4 -7 -6 10]
304 [ 2 -1 -7 -13 -6 5 3 -14 10 -9 -12 11 4 8]
305 [-11 -12 14 -5 4 -13 9 -10 -7 8 1 2 6 -3]
306 [ -9 3 -2 -6 -14 4 -13 11 1 12 -8 -10 7 5]
307 [-12 13 8 5 -4 -10 -14 -3 11 6 -9 1 -2 7]
308 [ 8 6 10 -14 -12 -2 11 -1 13 -3 -7 5 -9 4]
309 [ 14 -8 -11 6 9 -4 -10 2 -5 7 3 -13 12 -1]
310 [ -2 1 -6 13 12 3 -11 14 -10 9 7 -5 -4 -8]
311 [ 11 5 12 7 -2 9 -4 13 -6 14 -1 -3 -8 -10]
312 [ 6 10 11 -12 -7 -1 5 -9 8 -2 -3 4 -14 13]
313 [ 5 -13 -4 3 -1 8 -12 -6 14 11 -10 7 2 -9]
314 [-13 7 6 -9 14 -3 -2 -11 4 -12 8 10 1 -5]
315 [ -7 12 4 -3 6 -5 1 10 -11 -8 9 -2 14 -13]
316 [ 13 4 9 -2 8 -7 6 -5 -3 -11 10 -14 -1 12]]
317 """
318 days, n = y.shape # the number of days and teams to be scheduled
319 total: Final[int] = len(x)
320 index: int = 0
321 for day in range(days):
322 for slot in range(n):
323 other = int(y[day, slot])
324 if other > 0:
325 game_id = game_to_id(slot, other - 1, n)
326 for swap in range(index, total):
327 if x[swap] == game_id:
328 x[swap] = x[index]
329 x[index] = game_id
330 break
331 index += 1
334@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
335def map_games(x: np.ndarray, y: np.ndarray) -> None:
336 """
337 Translate a permutation of games to a game plan.
339 This is a straightforward decoding that places the games into the map one
340 by one. Each game is placed at the earliest slot in which it can be
341 placed. If a game cannot be placed, it is ignored. This will lead to many
342 errors, which can be counted via the :mod:`~moptipyapps.ttp.errors`
343 objective.
345 :param x: the source permutation
346 :param y: the destination game plan
348 >>> from moptipy.utils.nputils import int_range_to_dtype
349 >>> teams = 2
350 >>> rounds = 2
351 >>> perm = search_space_for_n_and_rounds(teams, rounds).blueprint
352 >>> print(perm)
353 [0 1]
354 >>> dest = np.empty((rounds * (teams - 1), teams),
355 ... int_range_to_dtype(-teams, teams))
356 >>> map_games(perm, dest)
357 >>> print(dest)
358 [[ 2 -1]
359 [-2 1]]
360 >>> perm[0] = 1
361 >>> perm[1] = 0
362 >>> re_encode(perm, dest)
363 >>> print(perm)
364 [0 1]
365 >>> map_games(perm, dest)
366 >>> print(dest)
367 [[ 2 -1]
368 [-2 1]]
369 >>> teams = 4
370 >>> rounds = 2
371 >>> perm = search_space_for_n_and_rounds(teams, rounds).blueprint
372 >>> dest = np.empty((rounds * (teams - 1), teams),
373 ... int_range_to_dtype(-teams, teams))
374 >>> map_games(perm, dest)
375 >>> print(dest)
376 [[ 2 -1 4 -3]
377 [ 3 4 -1 -2]
378 [ 4 3 -2 -1]
379 [-2 1 -4 3]
380 [-3 -4 1 2]
381 [-4 -3 2 1]]
382 >>> re_encode(perm, dest)
383 >>> print(perm)
384 [ 0 8 1 5 2 4 3 11 6 10 7 9]
385 >>> map_games(perm, dest)
386 >>> print(dest)
387 [[ 2 -1 4 -3]
388 [ 3 4 -1 -2]
389 [ 4 3 -2 -1]
390 [-2 1 -4 3]
391 [-3 -4 1 2]
392 [-4 -3 2 1]]
393 >>> from moptipyapps.ttp.instance import Instance
394 >>> inst = Instance.from_resource("circ10")
395 >>> perm = np.array([73,77,55,74,21,20,3,11,63,19,38,8,27,47,88,16,75,
396 ... 45,89,36,24,80,17,40,0,32,53,82,31,13,12,66,71,6,87,84,2,60,61,
397 ... 10,30,58,49,57,54,23,26,46,59,42,29,62,22,18,50,78,37,34,65,43,
398 ... 48,85,86,83,56,41,5,81,52,15,51,9,4,76,7,69,67,33,79,72,35,25,
399 ... 1,14,70,44,68,64,28,39])
400 >>> teams = 10
401 >>> rounds = 2
402 >>> dest = np.empty((rounds * (teams - 1), teams),
403 ... int_range_to_dtype(-teams, teams))
404 >>> map_games(perm, dest)
405 >>> print(dest)
406 [[ -8 -9 5 7 -3 10 -4 1 2 -6]
407 [ 5 -7 4 -3 -1 -9 2 -10 6 8]
408 [ 10 4 -9 -2 6 -5 8 -7 3 -1]
409 [ -4 -3 2 1 -7 8 5 -6 -10 9]
410 [ -6 9 -5 -8 3 1 -10 4 -2 7]
411 [ -5 10 -6 -9 1 3 -8 7 4 -2]
412 [ 2 -1 8 6 7 -4 -5 -3 10 -9]
413 [ 8 -10 6 5 -4 -3 9 -1 -7 2]
414 [ 4 6 7 -1 9 -2 -3 10 -5 -8]
415 [ -7 5 -8 -10 -2 9 1 3 -6 4]
416 [-10 3 -2 -7 -6 5 4 -9 8 1]
417 [ 0 -6 10 0 8 2 -9 -5 7 -3]
418 [ 9 -5 -4 3 2 -7 6 0 -1 0]
419 [ -3 8 1 9 0 0 10 -2 -4 -7]
420 [ -2 1 9 8 -10 7 -6 -4 -3 5]
421 [ 7 -8 -10 -6 -9 4 -1 2 5 3]
422 [ -9 -4 -7 2 -8 -10 3 5 1 6]
423 [ 6 7 0 10 0 -1 -2 9 -8 -4]]
424 >>> int(dest.shape[0] * dest.shape[1] - np.count_nonzero(dest))
425 8
426 >>> perm = np.array([21,32,53,63,73,3,20,55,77,88,8,11,40,60,74,19,27,51,
427 ... 58,89,16,38,45,66,87,17,36,47,69,75,0,24,31,41,80,6,22,30,61,82,
428 ... 2,13,23,43,71,12,52,54,65,84,10,49,57,79,81,1,28,44,68,78,7,26,
429 ... 39,59,64,18,34,42,46,62,9,25,33,50,85,5,15,48,76,83,14,29,67,72,
430 ... 86,4,35,37,56,70])
431 >>> dest.fill(0)
432 >>> map_games(perm, dest)
433 >>> print(dest)
434 [[ -8 -9 5 7 -3 10 -4 1 2 -6]
435 [ 5 -7 4 -3 -1 -9 2 -10 6 8]
436 [ 10 4 -9 -2 6 -5 8 -7 3 -1]
437 [ -4 -3 2 1 -7 8 5 -6 -10 9]
438 [ -6 9 -5 -8 3 1 -10 4 -2 7]
439 [ -5 10 -6 -9 1 3 -8 7 4 -2]
440 [ 2 -1 8 6 7 -4 -5 -3 10 -9]
441 [ 8 -10 6 5 -4 -3 9 -1 -7 2]
442 [ 4 6 7 -1 9 -2 -3 10 -5 -8]
443 [ -7 5 -8 -10 -2 9 1 3 -6 4]
444 [-10 3 -2 -7 -6 5 4 -9 8 1]
445 [ 3 -4 -1 2 10 -8 -9 6 7 -5]
446 [ 9 -8 10 -5 4 -7 6 2 -1 -3]
447 [ -3 -6 1 9 8 2 10 -5 -4 -7]
448 [ -2 1 9 8 -10 7 -6 -4 -3 5]
449 [ 7 8 -10 -6 -9 4 -1 -2 5 3]
450 [ -9 7 -4 3 -8 -10 -2 5 1 6]
451 [ 6 -5 -7 10 2 -1 3 9 -8 -4]]
452 """
453 y.fill(0) # first zero the output matrix
454 days, n = y.shape # the number of days and teams to be scheduled
455 div: Final[int] = n - 1 # the divisor for permutation values -> teams
457 for game in x:
458 g = int(game) # make sure that we have the full integer range.
459 home_idx: int = (g // div) % n # home idx is in 0..n-1
460 away_idx: int = g % div # away index in 0..n-2
461 if away_idx >= home_idx: # "A vs. A" games impossible
462 away_idx += 1 # away index in 0..n-1, but != home_idx
464 for day in range(days): # iterate over all possible rows for game
465 if (y[day, home_idx] != 0) or (y[day, away_idx] != 0):
466 continue # day already blocked
467 y[day, home_idx] = away_idx + 1
468 y[day, away_idx] = -(home_idx + 1)
469 break
472class GameEncoding(Encoding):
473 """An encoding that transforms strings of games to game plans."""
475 def __init__(self, instance: Instance) -> None:
476 """
477 Create the game-based encoding.
479 :param instance: the instance
480 """
481 super().__init__()
482 #: the instance
483 self.instance: Final[Instance] = instance
484 self.decode = map_games # type: ignore
486 def search_space(self) -> Permutations:
487 """
488 Create a proper search space for this game-based encoding.
490 The search space is a set of :mod:`~moptipy.spaces.permutations` that
491 represents all the games that can take place in the tournament.
492 Depending on the number of
493 :attr:`~moptipyapps.ttp.instance.Instance.rounds` in the tournament,
494 some games may appear multiple times. Home and away games are
495 distributed in a fair and deterministic mannner between the teams.
497 :return: the search space
499 >>> inst = Instance.from_resource("circ4")
500 >>> inst.n_cities
501 4
502 >>> inst.rounds
503 2
504 >>> ",".join(map(str, GameEncoding(inst).search_space().blueprint))
505 '0,1,2,3,4,5,6,7,8,9,10,11'
506 >>> inst = Instance(inst.name, inst, inst.teams, inst.rounds,
507 ... inst.home_streak_min, inst.home_streak_max,
508 ... inst.away_streak_min, inst.away_streak_max,
509 ... inst.separation_min, inst.separation_max)
510 >>> inst.rounds = 1 # modify number of rounds for copied instance
511 >>> ",".join(map(str, GameEncoding(inst).search_space().blueprint))
512 '1,2,3,7,8,10'
513 >>> inst.rounds = 3 # modify number of rounds for copied instance
514 >>> ",".join(map(str, GameEncoding(inst).search_space().blueprint))
515 '0,1,1,2,2,3,3,4,5,6,7,7,8,8,9,10,10,11'
516 >>> inst.rounds = 4 # modify number of rounds for copied instance
517 >>> ",".join(map(str, GameEncoding(inst).search_space().blueprint))
518 '0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11'
519 >>> inst.rounds = 5 # modify number of rounds for copied instance
520 >>> ",".join(map(str, GameEncoding(inst).search_space().blueprint))
521 '0,0,1,1,1,2,2,2,3,3,3,4,4,5,5,6,6,7,7,7,8,8,8,9,9,10,10,10,11,11'
522 """
523 return search_space_for_n_and_rounds(
524 self.instance.n_cities, self.instance.rounds)