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