Coverage for moptipy / spaces / signed_permutations.py: 88%
105 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2A search space for signed permutations of a base string.
4The base string can be a string where each element occurs exactly once,
5e.g., `[1, 2, 3]` or `[7, 2, 5]`. It could also be a string where some or
6all elements occur multiple times, e.g., a permutation with repetition, such
7as `[1, 7, 7, 4, 5, 3, 3, 3]` or `[3, 3, 1, 1, 2, 2]`. Each element may then
8occur either in its original (positive) value in a string or in its negated
9(negative) form.
11Notice that a signed permutation can never include the element `0`. Therefore,
12some methods have different semantics compared to those in class
13:class:`~moptipy.spaces.permutations.Permutations`.
15Search operators working on elements of this space are given in module
16:mod:`moptipy.operators.signed_permutations`, but several of those in
17:mod:`moptipy.operators.permutations` should work as well.
18"""
19from math import factorial
20from typing import Counter, Final, Iterable
22import numpy as np
23from pycommons.types import check_int_range, type_error
25from moptipy.spaces.intspace import IntSpace
26from moptipy.spaces.permutations import KEY_BASE_STRING, KEY_REPETITIONS
27from moptipy.utils.logger import KeyValueLogSection
28from moptipy.utils.nputils import array_to_str
29from moptipy.utils.strings import sanitize_name
31#: the unsigned minimum
32KEY_UNSIGNED_MIN: Final[str] = "unsignedMin"
35class SignedPermutations(IntSpace): # +book
36 """
37 Signed permutations of a base string stored as :class:`numpy.ndarray`.
39 This class includes standard permutations of the form 1, 2, ..., n,
40 but also permutations with repetitions.
41 The idea is that a base string is defined, i.e., an array of integer
42 values. In this array, some values may appear twice, some may be missing.
43 For example, `[1, 3, 5, 5, 7]` is a proper base string. The space defined
44 over this base string would then contain values such as `[1, 3, 5, 5, 7]`,
45 `[1, 5, 3, 5, 7]`, `[7, 5, 5, 3, 1]` and so on. Basically, it will contain
46 all strings that can be created by shuffling the base string *and/or*
47 negating some or all of the values, i.e., `[-1, 3, -5, 5, -7]` would also
48 be possible. These strings have in common that they contain exactly all the
49 values from the base string and contain them exactly as same as often as
50 they appear in the base string. They can never contain `0`.
52 The space defined upon the above base string contains
53 (2 ** 5) * 5! / (1! * 1! * 2! * 1!) = 32 * 120 / 2 = 1920
54 different strings.
56 The permutation space defined above can be created as follows:
58 >>> perm = SignedPermutations([1, 3, 5, 5, 7])
59 >>> print(perm.to_str(perm.blueprint))
60 1;3;5;5;7
61 >>> print(perm)
62 signedPermOfString
63 >>> print(perm.n_points())
64 1920
66 Another example is this:
68 >>> perm = SignedPermutations((1, 2, 3, 3, 2))
69 >>> print(perm.to_str(perm.blueprint))
70 1;2;2;3;3
71 >>> print(perm)
72 signedPermOfString
73 >>> print(perm.n_points())
74 960
76 If you want to create a permutation with repetitions, e.g.,
77 where each of the n=4 values from 1 to 4 appear exactly 3 times,
78 you can use the utility method `with_repetitions`:
80 >>> perm = SignedPermutations.with_repetitions(4, 3)
81 >>> print(perm.to_str(perm.blueprint))
82 1;1;1;2;2;2;3;3;3;4;4;4
83 >>> print(perm)
84 signedPerm4w3r
85 >>> print(perm.n_points())
86 1513881600
88 If you instead want to create standard permutations, i.e., where
89 each value from 1 to n appears exactly once, you would do:
91 >>> perm = SignedPermutations.standard(5)
92 >>> print(perm.to_str(perm.blueprint))
93 1;2;3;4;5
94 >>> print(perm)
95 signedPerm5
96 >>> print(perm.n_points())
97 3840
99 Different from normal permutations with repetitions, it is allowed
100 that signed permutations with repetitions contain the same element,
101 as long as their length is larger than 1.
103 >>> perm = SignedPermutations([1, 1])
104 >>> print(perm.to_str(perm.blueprint))
105 1;1
106 >>> x = perm.create()
107 >>> perm.validate(x)
108 >>> x[0] = -1
109 >>> perm.validate(x)
110 >>> x[1] = -1
111 >>> perm.validate(x)
112 >>> x[0] = 1
113 >>> perm.validate(x)
115 >>> try:
116 ... perm = SignedPermutations([1])
117 ... except ValueError as ve:
118 ... print(ve)
119 base_string must contain at least two different elements or have at \
120least length 2, but is [1].
121 """
123 def __init__(self, base_string: Iterable[int]) -> None: # +book
124 """
125 Create the space of signed permutations of a base string.
127 :param base_string: an iterable of integer to denote the base string
128 :raises TypeError: if one of the parameters has the wrong type
129 :raises ValueError: if the parameters have the wrong value
130 """
131 if not isinstance(base_string, Iterable):
132 raise type_error(base_string, "base_string", Iterable)
134 string: Final[list[int]] = sorted(abs(i) for i in base_string)
135 total: Final[int] = len(string)
136 if total <= 0:
137 raise ValueError(
138 f"base string must not be empty, but is {base_string}.")
140 # get data ranges
141 self.__shape: Final[Counter[int]] = Counter[int]()
142 minimum: int = string[0]
143 maximum: int = string[0]
144 for i in string:
145 if not isinstance(i, int):
146 raise type_error(i, "element of base_string", int)
147 self.__shape[i] += 1
148 minimum = min(minimum, i)
149 maximum = max(maximum, i)
151 # checking that the data is not empty
152 different: Final[int] = len(self.__shape)
153 if (total <= 1) and (different <= 1):
154 raise ValueError("base_string must contain at least two different"
155 " elements or have at least length 2, but is "
156 f"{base_string}.")
157 if minimum <= 0:
158 raise ValueError(f"base_string must only contain positive values,"
159 f" but minimum is {minimum}.")
161 # creating super class
162 super().__init__(total, -maximum, maximum)
164 #: a numpy array of the right type with the base string
165 self.blueprint: Final[np.ndarray] = \
166 np.array(string, dtype=self.dtype)
168 npoints: int = factorial(total)
169 rep: int | None = self.__shape.get(minimum)
170 for v in self.__shape.values():
171 npoints //= factorial(v)
172 if v != rep:
173 rep = None
174 #: the exact number of different signed permutations
175 self.__n_points = (2 ** len(string)) * npoints
177 #: the number of repetitions if all elements occur as same
178 #: as often, or None otherwise
179 self.__repetitions: Final[int | None] = rep
181 #: the unsigned minimum
182 self.unsigned_min_value: Final[int] = minimum
184 def has_repetitions(self) -> bool:
185 """
186 Return whether elements occur repeatedly in the base string.
188 :returns: `True` if at least one element occurs more than once,
189 `False` otherwise
190 """
191 return (self.__repetitions is None) or (self.__repetitions > 1)
193 def n(self) -> int:
194 """
195 Get the number of different values in the base string.
197 :returns: the number of different values in the base string
198 """
199 return len(self.__shape)
201 def is_dense(self) -> bool:
202 """
203 Check if all values in `min..max` appear in the permutation.
205 :returns: `True` if the permutation is dense in the sense that
206 all values from `self.min_value` to `self.max_value` appear.
207 """
208 return len(self.__shape) == (
209 self.max_value - self.unsigned_min_value + 1)
211 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
212 """
213 Log the parameters of this space to the given logger.
215 :param logger: the logger for the parameters
216 """
217 super().log_parameters_to(logger)
219 logger.key_value(KEY_UNSIGNED_MIN, self.unsigned_min_value)
221 reps: Final[int | None] = self.__repetitions
222 if reps:
223 logger.key_value(KEY_REPETITIONS, reps)
224 if self.is_dense():
225 return
226 logger.key_value(KEY_BASE_STRING,
227 array_to_str(self.blueprint))
229 def create(self) -> np.ndarray: # +book
230 r"""
231 Create a permutation equal to the base string.
233 The result is of the form [1, 1, 2, 2, 2, 3, 3...].
235 :return: the permutation of the base string
237 >>> perm = SignedPermutations([1, 5, 2, 2, 4, 3, 4])
238 >>> x = perm.create()
239 >>> print(perm.to_str(x))
240 1;2;2;3;4;4;5
241 """
242 return self.blueprint.copy() # Create copy of the blueprint.
244 def validate(self, x: np.ndarray) -> None:
245 """
246 Validate a signed permutation of the base string.
248 :param x: the integer string
249 :raises TypeError: if the string is not an :class:`numpy.ndarray`.
250 :raises ValueError: if the element is not a valid element of this
251 permutation space, e.g., if the shape or data type of `x` is
252 wrong, if an element is outside of the bounds, or if an
253 element does not occur exactly the prescribed amount of times
254 """
255 super().validate(x)
256 counts: Counter[int] = Counter[int]()
257 for xx in x:
258 if xx == 0:
259 raise ValueError("0 is not permitted in signed permutations.")
260 counts[abs(xx)] += 1
262 if counts != self.__shape:
263 for key in sorted(set(counts.keys()).union(
264 set(self.__shape.keys()))):
265 exp = self.__shape.get(key, 0)
266 found = counts.get(key, 0)
267 if found != exp:
268 raise ValueError(
269 f"Expected to find {key} exactly {exp} times "
270 f"but found it {found} times.")
272 def n_points(self) -> int:
273 """
274 Get the number of possible different permutations of the base string.
276 :return: (2 ** dimension) * factorial(dimension) /
277 Product(factorial(count(e)) for all e)
279 >>> print(SignedPermutations([1, 2, 3, 1, 2, 3]).n_points())
280 5760
281 """
282 return self.__n_points
284 def __str__(self) -> str:
285 """
286 Get the name of this space.
288 :return: "perm" + blueprint string
290 >>> print(SignedPermutations([3, 1, 5, 2, 1]))
291 signedPermOfString
292 >>> print(SignedPermutations([3, 2, 3, 1, 1, 2]))
293 signedPerm3w2r
294 >>> print(SignedPermutations([4, 2, 1, 3]))
295 signedPerm4
296 >>> print(SignedPermutations([3, 2, 4, 2, 3, 2, 4, 3, 4]))
297 signedPerm2to4w3r
298 """
299 minimum: Final[int] = self.unsigned_min_value
300 maximum: Final[int] = self.max_value
301 reps: Final[int | None] = self.__repetitions
302 different: Final[int] = self.n()
303 if reps and (different != (self.dimension // reps)):
304 raise ValueError(f"huh? {different} != {self.dimension} / {reps}")
305 all_values: Final[bool] = self.is_dense()
306 min_is_1: Final[bool] = minimum == 1
308 if reps:
309 if reps == 1:
310 if all_values:
311 if min_is_1:
312 return f"signedPerm{different}"
313 return sanitize_name(f"signedPerm{minimum}to{maximum}")
314 elif all_values: # repetitions != 1
315 if min_is_1:
316 return f"signedPerm{different}w{reps}r"
317 return sanitize_name(f"signedPerm{minimum}to{maximum}w{reps}r")
318 return "signedPermOfString"
320 @staticmethod
321 def standard(n: int) -> "SignedPermutations":
322 """
323 Create a space for permutations of `1..n`.
325 Notice that this method is different compared to the method
326 :meth:`~moptipy.spaces.permutations.Permutations.standard` of class
327 :class:`~moptipy.spaces.permutations.Permutations` in that it starts
328 the permutations at `1`, not at `0`.
330 :param n: the range of the values
331 :returns: the permutations space
332 """
333 return SignedPermutations(range(
334 1, 1 + check_int_range(n, "n", 2, 100_000_000)))
336 @staticmethod # +book
337 def with_repetitions(n: int, repetitions: int) -> "SignedPermutations":
338 """
339 Create a space for permutations of `1..n` with repetitions.
341 Notice that this method is different compared to the method
342 :meth:`~moptipy.spaces.permutations.Permutations.with_repetitions` of
343 class :class:`~moptipy.spaces.permutations.Permutations` in that it
344 starts the permutations at `1`, not at `0`.
346 :param n: the range of the values
347 :param repetitions: how often each value occurs
348 :returns: the permutations space
349 """
350 check_int_range(repetitions, "repetitions", 1, 1_000_000)
351 if repetitions <= 1:
352 return SignedPermutations.standard(n)
353 check_int_range(n, "n", 1, 100_000_000)
354 return SignedPermutations(list(range(1, 1 + n)) * repetitions)