Coverage for moptipy / operators / permutations / op1_swap_exactly_n.py: 63%
133 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2An operator trying to change exactly `n` elements in a permutation.
4This is an operator with a step size
5(:class:`moptipy.api.operators.Op1WithStepSize`) and the step size determines
6how many elements of a permutation should be changed.
7If you are working on permutations without repetitions, the operator in
8:mod:`~moptipy.operators.permutations.op1_swap_try_n` is the better and faster
9choice. On normal permutations, it will be equivalent to
10:mod:`~moptipy.operators.permutations.op1_swap_exactly_n`, but faster. On
11Permutations with repetitions, it will still be faster but less precisely
12enforces the number of swaps.
14Let's say we have a "normal" permutation where each element occurs once.
15The permutation has length `n`, let's say that its
16:attr:`~moptipy.spaces.permutations.Permutations.blueprint` is
17`[0, 1, 2, 3, 4, ..., n-1]`. Then, with one application of the operator, we
18can change no less than two elements (`step_size=0.0`) and no more than `n`
19(`step_size=1.0`). Clearly we cannot change only one element, because what
20different value could we put there? We would violate the "permutation nature."
21We can also not change more than `n` elements, obviously.
23What our operator does is then it computes `m` by using
24:func:`~moptipy.operators.tools.exponential_step_size`.
25This ensures that `m=2` for `step_size=0.0` and `m` is maximal for
26`step_size=1.0`. In between the two, it extrapolates exponentially. This means
27that small values of `step_size` will lead to few swap moves, regardless of
28the length of the permutation and many swaps are performed only for
29`step_size` values close to `1`.
30Then it will pick `m` random indices and permute the elements at them such
31that none remains at its current position.
32That is rather easy to do.
33Unfortunately, :class:`~moptipy.spaces.permutations.Permutations` allows also
34permutations with repetitions. Here, things get dodgy.
36Let's say we have the blueprint `[0, 1, 1, 1, 1]`. Then we can only change
37exactly two elements.
39>>> print(get_max_changes([0, 1, 1, 1, 1]))
402
42If we have the blueprint `[0, 0, 1, 1, 1]`, then we can change two elements.
43We can also change four elements. But there is no way to change three elements!
45>>> print(get_max_changes([0, 0, 1, 1, 1]))
464
48So in the general case, we determine the maximum number `mx` of positions that
49can be changed with one move via the function :func:`get_max_changes`.
50We can still translate a `step_size` to a number `m` by doing
51`m = 2 + int(round(step_size * (mx - 2)))`.
52However, it is not clear whether all moves from `m=2` to `m=mx` are actually
53possible.
55And even if they are possible, they might be very hard to sample randomly.
56Some moves touching a large number `m` of positions may be restricted to
57swap the elements at very specific indicies in a very specific order. Finding
58such a move by chance may be rather unlikely.
60Indeed, a search operator should do random moves. I did not find a way to
61construct moves according to a policy which is both random and can yield any
62move.
63So I divide the operator into two steps:
65First, the function :func:`find_move` tries to find a move for a given `m`
66in a random fashion. This function tries to find the sequence of indices for a
67cyclic swap where each element is different from both its successor and
68predecessor. It builds such index sequences iteratively. This may fail:
69as in the example above, for some values of `m` it might just not be
70possible to construct a suitable sequence, either because there is none or
71because building it randomly has too low of a chance of success. Hence, the
72function tries to build at most `max_trials` sequences. Whenever building a
73sequence, it also remembers the longest-so-far cyclic move. If that one is
74shorter than `m` but all `max_trials` trials are exhausted, it returns this
75sequence instead. So in summary, this function tries to find the longest
76cyclic swap which is not longer than `m` and returns it. It may be shorter
77than `m`. If we deal with permutations where each value occurs only once, this
78function is guaranteed to find a sequence of length `m` in the first trial,
79i.e., it does not waste runtime.
81Once a move was found, the function :func:`apply_move` applies it. Now, as
82said, :func:`find_move` discovers cyclic changes that are reasonably random.
83However, cyclic changes are not the only possible moves of length `m`. For
84example, if we have the permutation blueprint `[0, 1, 2, 3, 4]`, a move of
85length 4 could be to exchange `0` with `1` and to swap `2` with `3`.
86:func:`find_move` cannot find this move, but it could find a cyclic swap of
87`0` to `1`, `1` to `2`, `2` to `3`, and `3` to `1`. So it could find the
88right indices for such a move, just restricted to the cyclic swapping. So
89what :func:`apply_move` tries to do is to permute the indices discovered by
90:func:`find_move` randomly and check whether this would still yield a feasible
91move changing exactly `m` locations. Any shuffling of the elements at the
92selected position which avoids putting the original values into the original
93positions would do. Sometimes, most such shuffles work out, e.g., if we work
94on the space of permutations where each element occurs once. Sometimes, the
95only sequence that works is indeed the cyclic move and shuffling it cannot
96work. So :func:`apply_move` again has a limit for the maximum number of
97attempts to find a shuffle that works out. If it finds one, then it applies
98it as move. If it does not find one and the trials are exhausted, it randomly
99choses whether to apply the cyclic move as a cycle to the left or as a cycle
100to the right. Either way, it will change exactly `m` positions of the
101permutation, as prescribed by the move. Cycling one step in either direction
102will always work, since each element is different from both its predecessor
103and successor. (Cycling more than one step (but less than `m`) could
104potentially fail in permutations with repetitions, because there is no
105guarantee that any element is different from its successor's successor.)
107Now the overall operator just plugs these two functions together. It also adds
108one slight improvement: If we demand to change a number `q` of locations for
109the first time and :func:`find_move` fails to find a move of length `q` but
110instead offers one of length `p<q`, then the operator remembers this. The next
111time we ask to change `q` positions, it will directly try to change only `p`.
112This memory is reset in :meth:`~Op1SwapExactlyN.initialize`.
114A similar but much more light-weight and faster operator is given in
115:mod:`~moptipy.operators.permutations.op1_swap_try_n`. That operator also
116tries to perform a given number of swaps, but puts in much less effort to
117achieve this goal, i.e., it will only perform a single attempt.
118"""
119from typing import Counter, Final, Iterable
121import numba # type: ignore
122import numpy as np
123from numpy.random import Generator
124from pycommons.types import check_int_range, type_error
126from moptipy.api.operators import Op1WithStepSize
127from moptipy.operators.tools import exponential_step_size
128from moptipy.spaces.permutations import Permutations
129from moptipy.utils.logger import CSV_SEPARATOR, KeyValueLogSection
130from moptipy.utils.nputils import DEFAULT_INT, fill_in_canonical_permutation
133def get_max_changes(blueprint: Iterable[int]) -> int:
134 """
135 Get the maximum number of changes possible for a given permutation.
137 :param blueprint: the blueprint permutation
138 :returns: the maximum number of changes possible
140 >>> get_max_changes("1")
141 0
142 >>> get_max_changes("11")
143 0
144 >>> get_max_changes("12")
145 2
146 >>> get_max_changes("123")
147 3
148 >>> get_max_changes("1233")
149 4
150 >>> get_max_changes("12333")
151 4
152 >>> get_max_changes("1234")
153 4
154 >>> get_max_changes("12344")
155 5
156 >>> get_max_changes("123444")
157 6
158 >>> get_max_changes("1234444")
159 6
160 >>> get_max_changes("12334444")
161 8
162 >>> get_max_changes("123344445")
163 9
164 >>> get_max_changes("1233444455")
165 10
166 >>> get_max_changes("12334444555")
167 11
168 >>> get_max_changes("123344445555")
169 12
170 >>> get_max_changes("1233444455555")
171 13
172 >>> get_max_changes("12334444555555")
173 14
174 >>> get_max_changes("123344445555555")
175 15
176 >>> get_max_changes("1233444455555555")
177 16
178 >>> get_max_changes("12334444555555555")
179 16
180 >>> get_max_changes("112233")
181 6
182 >>> get_max_changes("11223344")
183 8
184 >>> get_max_changes("112233445")
185 9
186 >>> get_max_changes("1122334455")
187 10
188 >>> get_max_changes("11223344555")
189 11
190 >>> get_max_changes("112233445555555")
191 15
192 >>> get_max_changes("1122334455555555")
193 16
194 >>> get_max_changes("11223344555555555")
195 16
196 """
197 # Create tuples of (count, negative priority, value).
198 counts: Final[list[list[int]]] = [
199 [a[1], 0, a[0]] for a in Counter[int](blueprint).most_common()]
200 if len(counts) <= 1:
201 return 0
203# We simulate a chain swap. We begin with the element that appears the least
204# often. We take this element and reduce its count. Next, we take the element
205# that appears the most often. We reduce its count. And so on. Ties are broken
206# by prioritizing the element that was not used the longest. If the element
207# that we want to pick is the same as the previously picked one, we skip over
208# it. If no element can be picked, we quit.
209 changes: int = 0
210 last: int | None = None
211 found: bool = True
212 smallest: bool = True
213 while found:
214 found = False
215# We sort alternatingly sometimes we pick the smallest, sometimes the largest.
216 if smallest:
217 counts.sort()
218 else:
219 counts.sort(key=lambda a: [-a[0], a[1]])
220 smallest = not smallest # realize the alternating sorting
221# Now we iterate over the sorted list and pick the first suitable element.
222# I know: There will be at most two iterations of this loop ... but whatever.
223 for idx, chosen in enumerate(counts):
224 current = chosen[2]
225 if current == last: # We cannot pick the same element twice
226 continue # in a row. So we skip over it.
227 cnt = chosen[0]
228 if cnt <= 1: # How often does this element exist in the list?
229 del counts[idx] # noqa
230 else:
231 chosen[0] = cnt - 1 # noqa
232 changes += 1 # Yeah, we can increase the changes.
233 chosen[1] = changes # Increase negative priority.
234 found = True # We found an element.
235 last = current # Remember the element.
236 break # Quit (after at most two loop iterations).
237 if changes <= 1: # This cannot be.
238 raise ValueError(
239 f"Error in counting possible changes for {blueprint}.")
240 return changes
243@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
244def find_move(x: np.ndarray, indices: np.ndarray, step_size: int,
245 random: Generator, max_trials: int,
246 temp: np.ndarray) -> np.ndarray:
247 """
248 Find a move of at most step_size changes and store it in indices.
250 For any pure permutation `x`, we can basically find any move between
251 `step_size=2` and `len(x)`. If we have permutations with repetitions, the
252 upper limit becomes smaller, because it may not be possible to change all
253 elements at once. For example, in `[0, 0, 1, 1, 1, 1, 1]`, we can change
254 at most four elements. For this purpose, :func:`get_max_changes` exists.
255 It tells us the upper limit of changes, which would be four here:
257 >>> print(get_max_changes([0, 0, 1, 1, 1, 1, 1]))
258 4
260 Yet, this does not necessarily mean that we can make all moves including
261 2, 3, and 4 changes. If you look at the above example, you may find that
262 it is impossible to change exactly 3 locations. We can only actually do
263 step sizes of 2 and 4, but neither 3 nor 5, 6, nor 7.
264 In reality, even if it was possible to make a big move, it might be very
265 unlikely to be able to this in a *random* fashion. If you look at the
266 code of :func:`get_max_changes`, it tries to find the longest possible
267 cyclic move by working through the elements of the permutation in a very
268 specific order. Using a different (or random) order would yield shorter
269 moves.
271 Our method :func:`find_move` here therefore tries to find the longest
272 possible cyclic swap involving at most `step_size` indices. It may find
273 such a move that uses exactly `step_size` indices. But it may also find
274 a shorter move because either the perfect complete feasible move touching
275 `step_size` indices does not exist or because finding it in a random
276 fashion may take too long. (For this purpose, `max_trials` exists to
277 limit the search for the right move.)
279 For normal permutations, it will find the move of exactly the right
280 length. For permutations with repetitions, it has a decent chance to find
281 a move of the length `step_size` if a) such a move exists and
282 b) `step_size` is not too big. Otherwise, it should find a shorter but
283 still reasonably large move.
285 :param x: the permutation to be modified in the end
286 :param indices: the set of indices, which must be the canonical
287 permutation of `0...len(x)-1`
288 :param step_size: the step size, i.e., the number of elements to change
289 :param random: the random number generator
290 :param max_trials: the maximum number of trials
291 :param temp: a temporary array
292 :returns: the discovered move
294 >>> import numpy as npx
295 >>> from numpy.random import default_rng
296 >>> gen = default_rng(12)
297 >>> perm = npx.array([0, 1, 2, 3, 3, 3, 3, 3, 3], int)
298 >>> use_indices = npx.array(range(len(perm)), int)
299 >>> want_size = len(perm)
300 >>> print(want_size)
301 9
302 >>> print(get_max_changes(perm))
303 6
304 >>> use_temp = npx.empty(len(perm), int)
305 >>> res = find_move(perm, use_indices, want_size, gen, 1000, use_temp)
306 >>> print(res)
307 [5 2 8 1 4 0]
308 >>> perm2 = perm.copy()
309 >>> perm2[res] = perm2[npx.roll(res, 1)]
310 >>> print(f"{perm} vs. {perm2}")
311 [0 1 2 3 3 3 3 3 3] vs. [3 3 3 3 1 0 3 3 2]
312 >>> print(sum(perm != perm2))
313 6
314 >>> perm = npx.array([1, 3, 5, 9, 4, 2, 11, 7], int)
315 >>> want_size = len(perm)
316 >>> print(want_size)
317 8
318 >>> use_indices = npx.array(range(len(perm)), int)
319 >>> use_temp = npx.empty(len(perm), int)
320 >>> res = find_move(perm, use_indices, want_size, gen, 1, use_temp)
321 >>> print(res)
322 [4 0 5 3 1 7 2 6]
323 >>> print(len(res))
324 8
325 >>> perm2 = perm.copy()
326 >>> perm2[res] = perm2[npx.roll(res, 1)]
327 >>> print(f"{perm} vs. {perm2}")
328 [ 1 3 5 9 4 2 11 7] vs. [ 4 9 7 2 11 1 5 3]
329 >>> print(sum(perm != perm2))
330 8
331 """
332 length: Final[int] = len(x)
333 lm1: Final[int] = length - 1
334 sm1: int = step_size - 1
335 best_size: int = -1
337# We spent at most `max_trials` trials to find a perfect move. The reason is
338# that some values of `step_size` might be impossible to achieve, other may
339# be achievable only with a very low probability. So we need a trial limit to
340# avoid entering a very long or even endless loop.
341 for _ in range(max_trials):
342 current_best_size: int = -1 # longest feasible move this round
343# We aim to store a suitable selection of indices at indices[0:step_size].
344# Like in :mod:`moptipy.operators.permutations.op1_swapn`, we try to create a
345# feasible move as a series of cyclic swaps. Basically, the element at index
346# i1 would be moved to index i2, the element at i2 to i3, ..., the element at
347# the last index ix to i1. We make sure that all indices are used at most
348# once.
349# We proceed similar to a partial Fisher-Yates shuffle.
350# The variable "found" is the number of indices that we have fixed so far.
351# For each new position, we test the remaining indices in random order.
352# An index can only be used if it points to an element different to what the
353# last index points to, or else the cyclic swap would be meaningless.
354# For the last index to be chosen, that element must also be different from
355# the first element picked.
356# So a potential index may not work. We test each index at most once by moving
357# the tested indices into the range indices[found:tested] and keep increasing
358# tested and reset it once we found a new acceptable index.
359# This procedure, however, may end up in a dead end. We therefore need to wrap
360# it into a loop that tries until success... ...but we cannot do that because
361# success may not be possible. Some moves may be impossible to do.
362 i_idx = random.integers(0, length) # Get the first random index.
363 i_src = indices[i_idx] # Pick the actual index at that index.
364 indices[0], indices[i_idx] = i_src, indices[0] # Swap it to 0.
365 found: int = 1 # the number of found indices
366 tested: int = 1 # the number of tested indices
367 last = first = x[i_src] # Get the value at the first index.
368 continue_after: bool = found < sm1 # continue until step_size-1
369 while True:
370 i_idx = random.integers(tested, length) # Get random index.
371 i_dst = indices[i_idx] # Pick the actual index.
372 current = x[i_dst] # Get value at the new index.
373 can_end: bool = current != first
374 accept: bool = (current != last) and (continue_after or can_end)
375 if accept:
376 # Now we move the new index into the "found" section.
377 indices[found], indices[i_idx] = i_dst, indices[found]
378 tested = found = found + 1 # found++, reset tested.
379 last = current # Store value from i_dst in last.
380 if can_end:
381 current_best_size = found
382 if not continue_after:
383 return indices[0:found] # We won!
384 continue_after = found < sm1 # continue until step_size-1
385 continue
386 if tested >= lm1: # Are we in a dead end?
387 break # and try again freshly.
388 indices[tested], indices[i_idx] = i_dst, indices[tested]
389 tested += 1 # We have tested another value.
391# If we get here, we did not succeed in creating a complete move this round.
392# However, current_best_size should indicate one possible shorter move.
393# It must be at least >= 2, because we will definitely be able to find two
394# different elements in x. We will remember the longest feasible move
395# discovered in all max_trials iterations.
396 if current_best_size > best_size:
397 best_size = current_best_size
398 temp[0:best_size] = indices[0:best_size]
400# If get here, we have completed the main loop. We could not find a complete
401# feasible move that changes exactly step_size locations. However, we should
402# have a shorter move by now stored in temp. So we copy its indices.
403 return temp[0:best_size]
406@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
407def apply_move(x: np.ndarray, dest: np.ndarray, move: np.ndarray,
408 random: Generator, max_trials: int) -> None:
409 """
410 Apply a given move copying from source `x` to `dest`.
412 `move` must be the return value of :func:`find_move`.
414 :param x: the source permutation
415 :param dest: the destination permutation
416 :param move: the move of length `step_size`
417 :param random: the random number generator
418 :param max_trials: a maximum number of trials
420 >>> import numpy as npx
421 >>> from numpy.random import default_rng
422 >>> rand = default_rng(12)
423 >>> xx = npx.array([0, 1, 2, 3, 3, 3, 3, 3, 3], int)
424 >>> dd = npx.empty(len(xx), int)
425 >>> mv = npx.array([5, 2, 8, 1, 4, 0], int)
426 >>> print(len(mv))
427 6
428 >>> apply_move(xx, dd, mv, rand, 0)
429 >>> print(dd)
430 [3 3 3 3 0 2 3 3 1]
431 >>> print(sum(dd != xx))
432 6
433 >>> apply_move(xx, dd, mv, rand, 1000)
434 >>> print(dd)
435 [3 3 3 3 2 1 3 3 0]
436 >>> print(sum(dd != xx))
437 6
438 >>> xx = npx.array([1, 3, 5, 9, 4, 2, 11, 7], int)
439 >>> dd = npx.empty(len(xx), int)
440 >>> mv = npx.array([4, 0, 5, 3, 1, 7, 2, 6], int)
441 >>> print(len(mv))
442 8
443 >>> apply_move(xx, dd, mv, rand, 0)
444 >>> print(dd)
445 [ 4 9 7 2 11 1 5 3]
446 >>> print(sum(dd != xx))
447 8
448 >>> xx = npx.array([1, 3, 5, 9, 4, 2, 11, 7], int)
449 >>> apply_move(xx, dd, mv, rand, 10)
450 >>> print(dd)
451 [ 5 4 2 11 7 3 9 1]
452 >>> print(sum(dd != xx))
453 8
454 """
455 dest[:] = x[:] # First, we copy `x` to `dest`.
456 step_size: Final[int] = len(move) # Get the move size.
457# We now try to replace the sub-string x[move] with a random permutation of
458# itself. Since `move` is the return value of `find_move`, we know that it
459# could be realized as a cyclic swap. However, we are not yet sure whether it
460# can also be some other form of move, maybe swapping a few pairs of elements.
461# We try to find this out in this loop by testing `max_trials` random
462# permutations of the original subsequence.
463 orig: np.ndarray = dest[move] # Get the original subsequence.
464 perm: np.ndarray = orig.copy()
465 for _ in range(max_trials): # Try to permute it.
466 random.shuffle(perm) # Shuffle the permutation
467 if sum(perm != orig) == step_size: # If all elements are now...
468 dest[move] = perm # ...at different places, accept the move and
469 return # quit
470# If we get here, trying random permutations of the sequence did not work.
471# We now simply perform a cyclic swap. A cyclic swap has the property that
472# each element is different from both its predecessor and its successor.
473# Hence, we could cycle left or cycle right. Now one could argue that this
474# should not matter, since we have constructed the move in a random way via
475# find_move. However, I am not sure. If we have a permutation with repetition,
476# then finding certain move patterns could be more likely than others. For
477# example, if one element occurs much more often than another one, one of its
478# instance could be more likely chosen as first element of the move. A more
479# rarely occurring element could then appear later in the move when there are
480# not many other choices left. Hence, it might be that the moves found by
481# find_move are not uniformly distributed over the realm of possible moves of
482# a given step length. In this case, it may be useful to randomly choose
483# whether to cycle left or right. We cannot cycle more than one step, though,
484# because there is guarantee that an element is different from its successor's
485# successor.
486 dest[move] = np.roll(orig, 1 if random.integers(0, 2) == 0 else -1)
489class Op1SwapExactlyN(Op1WithStepSize):
490 """A unary search operator that swaps `n` (different) elements."""
492 def __init__(self, perm: Permutations,
493 max_move_trials: int = 1000,
494 max_apply_trials: int = 1000) -> None:
495 """
496 Initialize the operator.
498 :param perm: the base permutation
499 :param max_move_trials: the maximum number of attempts to generate a
500 fitting move
501 :param max_apply_trials: the maximum number of attempts to apply a
502 move via a random permutation
503 """
504 super().__init__()
505 if not isinstance(perm, Permutations):
506 raise type_error(perm, "perm", Permutations)
508# If each value appears exactly once in the permutation, then we can
509# easily do perm.dimension changes. If the permutation is with
510# repetitions, then it might be fewer, so we need to check.
511 is_pure_perm: Final[bool] = perm.n() == perm.dimension
512 #: the maximum number of possible changes
513 self.max_changes: Final[int] = check_int_range(
514 perm.dimension if is_pure_perm
515 else get_max_changes(perm.blueprint),
516 "max_changes", 2, 100_000_000)
517 #: the maximum number of attempts to find a move with the exact step
518 #: size
519 self.max_move_trials: Final[int] =\
520 check_int_range(max_move_trials, "max_move_trials", 1)
521 #: the maximum number of attempts to apply a random permutation of the
522 #: move before giving up and applying it as cyclic swap
523 self.max_apply_trials: Final[int] =\
524 check_int_range(max_apply_trials, "max_apply_trials", 1)
525 #: the set of chosen indices
526 self.__indices: Final[np.ndarray] = np.empty(
527 perm.dimension, DEFAULT_INT)
528 #: a temporary array
529 self.__temp: Final[np.ndarray] = np.empty(
530 perm.dimension, DEFAULT_INT)
531 #: the initial move map that maps step sizes to feasible sizes
532 self.__initial_move_map: Final[dict[int, int]] = {i: i for i in range(
533 2, perm.dimension + 1)} if is_pure_perm else {2: 2}
534 #: the move map that maps step sizes to feasible sizes
535 self.__move_map: Final[dict[int, int]] = {}
537 def initialize(self) -> None:
538 """Initialize this operator."""
539 super().initialize()
540 fill_in_canonical_permutation(self.__indices)
541 self.__move_map.clear()
542 self.__move_map.update(self.__initial_move_map)
544 def op1(self, random: Generator, dest: np.ndarray, x: np.ndarray,
545 step_size: float = 0.0) -> None:
546 """
547 Copy `x` into `dest` and then swap several different values.
549 :param random: the random number generator
550 :param dest: the array to receive the modified copy of `x`
551 :param x: the existing point in the search space
552 :param step_size: the number of elements to swap
553 """
554# compute the real step size based on the maximum changes
555 use_step_size: int = exponential_step_size(
556 step_size, 2, self.max_changes)
557# look up in move map: Do we already know whether this step size works or can
558# it be replaced with a similar smaller one?
559 move_map: Final[dict[int, int]] = self.__move_map
560 mapped_step_size = move_map.get(use_step_size, -1)
561 if mapped_step_size >= 2:
562 use_step_size = mapped_step_size
564 move: Final[np.ndarray] = find_move(
565 x, self.__indices, use_step_size, random, self.max_move_trials,
566 self.__temp)
568# If we did not yet know the move size, then update it.
569 if mapped_step_size == -1:
570 self.__move_map[use_step_size] = len(move)
571 self.__move_map[use_step_size] = use_step_size
572# Finally, apply the move.
573 apply_move(x, dest, move, random, self.max_move_trials)
575 def __str__(self) -> str:
576 """
577 Get the name of this unary operator.
579 :returns: "swapxn", the name of this operator
580 :retval "swapxn": always
581 """
582 return "swapxn"
584 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
585 """
586 Log the parameters of this operator to the given logger.
588 :param logger: the logger for the parameters
589 """
590 super().log_parameters_to(logger)
591 logger.key_value("maxChanges", self.max_changes)
592 logger.key_value("maxMoveTrials", self.max_move_trials)
593 logger.key_value("maxApplyTrials", self.max_apply_trials)
595# Translate the move map to some strings like "2;5-8;12", meaning that all the
596# moves 2, 5, 6, 7, 8, and 12 were performed and valid.
597 kvs: list[int] = [k for k, v in self.__move_map.items() if k == v]
598 kvs.sort()
599 lk: Final[int] = len(kvs) - 1
600 kvs = [(e if ((i <= 0) or (i >= lk) or kvs[i - 1] != (e - 1))
601 or (kvs[i + 1] != (e + 1)) else -1)
602 for i, e in enumerate(kvs)]
603 kvs = [e for i, e in enumerate(kvs) if
604 (i <= 0) or (i >= lk) or (e != -1) or (kvs[i - 1] != -1)]
605 logger.key_value("moves", CSV_SEPARATOR.join(
606 "-" if k < 0 else str(k) for k in kvs).replace(
607 f"{CSV_SEPARATOR}-{CSV_SEPARATOR}", "-"))