Coverage for moptipy / spaces / permutations.py: 88%
99 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2An implementation of a search space for permutations of a base string.
4The base string can be a string where each element occurs exactly once,
5e.g., `[0, 1, 2, 3]` or `[0, 7, 2, 5]`. It could also be a string where
6some or all elements occur multiple times, e.g., a permutation with
7repetition, such as `[0, 7, 7, 4, 5, 3, 3, 3]` or `[0, 0, 1, 1, 2, 2]`.
8Search operators working on elements of this space are given in module
9:mod:`moptipy.operators.permutations`.
10"""
11from math import factorial
12from typing import Counter, Final, Iterable
14import numpy as np
15from pycommons.types import check_int_range, type_error
17from moptipy.spaces.intspace import IntSpace
18from moptipy.utils.logger import KeyValueLogSection
19from moptipy.utils.nputils import array_to_str
20from moptipy.utils.strings import sanitize_name
22#: the base string to be permuted
23KEY_BASE_STRING: Final[str] = "baseString"
24#: the number of times each value must occur
25KEY_REPETITIONS: Final[str] = "repetitions"
28class Permutations(IntSpace): # +book
29 """
30 A space of permutations of a base string stored as :class:`numpy.ndarray`.
32 This class includes standard permutations of the form 0, 1, 2, ..., n-1,
33 but also permutations with repetitions.
34 The idea is that a base string is defined, i.e., an array of integer
35 values. In this array, some values may appear twice, some may be missing.
36 For example, `[1, 3, 5, 5, 7]` is a proper base string. The space defined
37 over this base string would then contain values such as `[1, 3, 5, 5, 7]`,
38 `[1, 5, 3, 5, 7]`, `[7, 5, 5, 3, 1]` and so on. Basically, it will contain
39 all strings that can be created by shuffling the base string. These
40 strings have in common that they contain exactly all the values from the
41 base string and contain them exactly as same as often as they appear in
42 the base string. The space defined upon the above base string therefore
43 would contain 5! / (1! * 1! * 2! * 1!) = 120 / 2 = 60 different strings.
45 The permutation space defined above can be created as follows:
47 >>> perm = Permutations([1, 3, 5, 5, 7])
48 >>> print(perm.to_str(perm.blueprint))
49 1;3;5;5;7
50 >>> print(perm)
51 permOfString
52 >>> print(perm.n_points())
53 60
55 Another example is this:
57 >>> perm = Permutations((1, 2, 3, 3, 2))
58 >>> print(perm.to_str(perm.blueprint))
59 1;2;2;3;3
60 >>> print(perm)
61 permOfString
62 >>> print(perm.n_points())
63 30
65 If you want to create a permutation with repetitions, e.g.,
66 where each of the n=4 values from 0 to 3 appear exactly 3 times,
67 you can use the utility method `with_repetitions`:
69 >>> perm = Permutations.with_repetitions(4, 3)
70 >>> print(perm.to_str(perm.blueprint))
71 0;0;0;1;1;1;2;2;2;3;3;3
72 >>> print(perm)
73 perm4w3r
74 >>> print(perm.n_points())
75 369600
77 If you instead want to create standard permutations, i.e., where
78 each value from 0 to n-1 appears exactly once, you would do:
80 >>> perm = Permutations.standard(5)
81 >>> print(perm.to_str(perm.blueprint))
82 0;1;2;3;4
83 >>> print(perm)
84 perm5
85 >>> print(perm.n_points())
86 120
87 """
89 def __init__(self, base_string: Iterable[int]) -> None: # +book
90 """
91 Create the space of permutations of a base string.
93 :param base_string: an iterable of integer to denote the base string
94 :raises TypeError: if one of the parameters has the wrong type
95 :raises ValueError: if the parameters have the wrong value
96 """
97 if not isinstance(base_string, Iterable):
98 raise type_error(base_string, "base_string", Iterable)
100 string: Final[list[int]] = sorted(base_string)
101 total: Final[int] = len(string)
102 if total <= 0:
103 raise ValueError(
104 f"base string must not be empty, but is {base_string}.")
106 # get data ranges
107 self.__shape: Final[Counter[int]] = Counter[int]()
108 minimum: int = string[0]
109 maximum: int = string[0]
110 for i in string:
111 if not isinstance(i, int):
112 raise type_error(i, "element of base_string", int)
113 self.__shape[i] += 1
114 minimum = min(minimum, i)
115 maximum = max(maximum, i)
117 # checking that the data is not empty
118 different: Final[int] = len(self.__shape)
119 if different <= 1:
120 raise ValueError(
121 "base_string must contain at least two different "
122 f"elements, but is {base_string}.")
124 # creating super class
125 super().__init__(total, minimum, maximum)
127 # start book
128 #: a numpy array of the right type with the base string
129 self.blueprint: Final[np.ndarray] = \
130 np.array(string, dtype=self.dtype)
131 # end book
133 npoints: int = factorial(total)
134 rep: int | None = self.__shape.get(minimum)
135 for v in self.__shape.values():
136 npoints //= factorial(v)
137 if v != rep:
138 rep = None
139 #: the exact number of different permutations
140 self.__n_points = npoints
142 #: the number of repetitions if all elements occur as same
143 #: as often, or None otherwise
144 self.__repetitions: Final[int | None] = rep
146 def has_repetitions(self) -> bool:
147 """
148 Return whether elements occur repeatedly in the base string.
150 :returns: `True` if at least one element occurs more than once,
151 `False` otherwise
152 """
153 return (self.__repetitions is None) or (self.__repetitions > 1)
155 def n(self) -> int:
156 """
157 Get the number of different values in the base string.
159 :returns: the number of different values in the base string
160 """
161 return len(self.__shape)
163 def is_dense(self) -> bool:
164 """
165 Check if all values in `min..max` appear in the permutation.
167 :returns: `True` if the permutation is dense in the sense that
168 all values from `self.min_value` to `self.max_value` appear.
169 """
170 return len(self.__shape) == (self.max_value - self.min_value + 1)
172 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
173 """
174 Log the parameters of this space to the given logger.
176 :param logger: the logger for the parameters
177 """
178 super().log_parameters_to(logger)
180 reps: Final[int | None] = self.__repetitions
181 if reps:
182 logger.key_value(KEY_REPETITIONS, reps)
183 if self.is_dense():
184 return
185 logger.key_value(KEY_BASE_STRING,
186 array_to_str(self.blueprint))
188 def create(self) -> np.ndarray: # +book
189 r"""
190 Create a permutation equal to the base string.
192 The result is of the form [0, 0, 1, 1, 1, 2, 2...].
194 :return: the permutation of the base string
196 >>> perm = Permutations([1, 5, 2, 2, 4, 3, 4])
197 >>> x = perm.create()
198 >>> print(perm.to_str(x))
199 1;2;2;3;4;4;5
200 """
201 return self.blueprint.copy() # Create copy of the blueprint. # +book
203 def validate(self, x: np.ndarray) -> None:
204 """
205 Validate a permutation of the base string.
207 :param x: the integer string
208 :raises TypeError: if the string is not an :class:`numpy.ndarray`.
209 :raises ValueError: if the element is not a valid element of this
210 permutation space, e.g., if the shape or data type of `x` is
211 wrong, if an element is outside of the bounds, or if an
212 element does not occur exactly the prescribed amount of times
213 """
214 super().validate(x)
215 counts: Counter[int] = Counter[int]()
216 for xx in x:
217 counts[xx] += 1
219 if counts != self.__shape:
220 for key in sorted(set(counts.keys()).union(
221 set(self.__shape.keys()))):
222 exp = self.__shape.get(key, 0)
223 found = counts.get(key, 0)
224 if found != exp:
225 raise ValueError(
226 f"Expected to find {key} exactly {exp} times "
227 f"but found it {found} times.")
229 def n_points(self) -> int:
230 """
231 Get the number of possible different permutations of the base string.
233 :return: factorial(dimension) / Product(factorial(count(e)) for all e)
235 >>> print(Permutations([0, 1, 2, 3, 0, 1, 2, 3]).n_points())
236 2520
237 """
238 return self.__n_points
240 def __str__(self) -> str:
241 """
242 Get the name of this space.
244 :return: "perm" + blueprint string
246 >>> print(Permutations([0, 1, 0, 2, 1]))
247 permOfString
248 >>> print(Permutations([0, 2, 0, 1, 1, 2]))
249 perm3w2r
250 >>> print(Permutations([0, 2, 1, 3]))
251 perm4
252 >>> print(Permutations([3, 2, 4, 2, 3, 2,4, 3, 4]))
253 perm2to4w3r
254 """
255 minimum: Final[int] = self.min_value
256 maximum: Final[int] = self.max_value
257 reps: Final[int | None] = self.__repetitions
258 different: Final[int] = self.n()
259 if reps and (different != (self.dimension // reps)):
260 raise ValueError(f"huh? {different} != {self.dimension} / {reps}")
261 all_values: Final[bool] = self.is_dense()
262 min_is_0: Final[bool] = minimum == 0
264 if reps:
265 if reps == 1:
266 if all_values:
267 if min_is_0:
268 return f"perm{different}"
269 return sanitize_name(f"perm{minimum}to{maximum}")
270 elif all_values: # repetitions != 1
271 if min_is_0:
272 return f"perm{different}w{reps}r"
273 return sanitize_name(f"perm{minimum}to{maximum}w{reps}r")
274 return "permOfString"
276 @staticmethod
277 def standard(n: int) -> "Permutations":
278 """
279 Create a space for permutations of 0..n-1.
281 :param n: the range of the values
282 :returns: the permutations space
283 """
284 return Permutations(range(check_int_range(n, "n", 2, 100_000_000)))
286 @staticmethod # +book
287 def with_repetitions(n: int, repetitions: int) -> "Permutations": # +book
288 """
289 Create a space for permutations of `0..n-1` with repetitions.
291 :param n: the range of the values
292 :param repetitions: how often each value occurs
293 :returns: the permutations space
294 """
295 check_int_range(repetitions, "repetitions", 1, 1_000_000)
296 if repetitions <= 1:
297 return Permutations.standard(n)
298 check_int_range(n, "n", 1, 100_000_000)
299 return Permutations(list(range(n)) * repetitions) # +book