Coverage for moptipy / spaces / ordered_choices.py: 92%
89 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2Permutations of a selection (or ordered choices) as strings.
4Imagine the following situation: We have a rectangle (two-dimensional) and
5want to place `n` other, smaller rectangles into it. Let each rectangle have
6a unique ID from `1` to `n`. We can use a permutation of `1..n` to represent
7the order in which we insert the small rectangles. However, maybe we want to
8also be able to rotate a rectangle by 90° and then place it. So additionally
9to the insertion order, we may want to remember whether the rectangle is
10placed as-is or rotated. We could do this with a "permutation of choices",
11where we can place either `i` or `-i` for `i` from `1..n`. A negative value
12could mean "insert rotated by 90°" whereas a positive value means "insert as
13is". So we have `n` (disjoint) choices, each of which with two options. From
14each choice, we can pick one value. Then the order in which the values appear
15marks the insertion order. So this is basically a "super space" of
16permutations, as it deals both with the order of the elements and their values
17(resulting from the selected choice).
19A string consists of `n` elements. There also are `n` so-called "selections,"
20each of which being a set offering a choice from different values. Any two
21selections must either be entirely disjoint or equal. The final string must
22contain one value from each selection.
24Let's say that we have three selections, e.g., `[1, 2, 3]`, `[4, 5]`, and
25`[6]`. Then the "selection permutations" space contains, e.g., the string
26`[4, 3, 6]` or `[2, 5, 6]` -- one value from each selection. It does not
27contain `[1, 3, 5]`, though, because that string has two values from the first
28selection.
30This space is a super space of the :mod:`~moptipy.spaces.permutations`, i.e.,
31the space of permutations with repetitions. Sometimes (check
32:meth:`OrderedChoices.is_compatible_with_permutations`), the search
33operators defined in package :mod:`~moptipy.operators.permutations` can also
34be applied to the elements of our space here, although they may not be able
35to explore the space in-depth (as they will not alter the choices and only
36permute the chosen elements).
37"""
38from collections import Counter
39from math import factorial
40from typing import Final, Iterable
42import numpy as np
43from pycommons.types import type_error
45from moptipy.spaces.intspace import IntSpace
46from moptipy.utils.logger import CSV_SEPARATOR, KeyValueLogSection
47from moptipy.utils.nputils import array_to_str
49#: the different choices
50KEY_CHOICES: Final[str] = "choices"
53class OrderedChoices(IntSpace):
54 """Permutations of selections, stored as :class:`numpy.ndarray`."""
56 def __init__(self, selections: Iterable[Iterable[int]]) -> None:
57 """
58 Create the space of permutations of selections.
60 :param selections: an iterable of selections
61 :raises TypeError: if one of the parameters has the wrong type
62 :raises ValueError: if the parameters have the wrong value
63 """
64 if not isinstance(selections, Iterable):
65 raise type_error(selections, "selections", Iterable)
67 sets: Final[dict[int, tuple[int, ...]]] = {}
69 min_v: int = 0
70 max_v: int = 0
71 total: int = 0
72 counts: Counter[tuple[int, ...]] = Counter()
73 blueprint: Final[list[int]] = []
75 for i, sel in enumerate(selections):
76 total += 1
77 if not isinstance(sel, Iterable):
78 raise type_error(sel, f"selections[{i}]", Iterable)
79 sel_lst = tuple(sorted(sel))
80 len_sel = len(sel_lst)
81 if len_sel <= 0:
82 raise ValueError(f"empty selection at index {i}: {sel}.")
83 sel_set = set(sel_lst)
84 if len(sel_set) != len_sel:
85 raise ValueError(f"invalid selection {sel} at index {i} "
86 f"contains duplicate element")
87 blueprint.append(sel_lst[0])
88 # build the selection map
89 for e in sel_lst:
90 if not isinstance(e, int):
91 raise type_error(e, f"selections[{i}]={sel}", int)
92 if e in sets:
93 lst_found = sets[e]
94 if lst_found != sel_lst:
95 raise ValueError(
96 f"value {e} appears both in selection {sel_lst} "
97 f"(at permutation index {i}) and in selection "
98 f"{lst_found}!")
99 sel_lst = lst_found
100 continue # if any sets[e] != sel_lst, we get error anyway
101 sets[e] = sel_lst # remember value
102 counts[sel_lst] += 1
104 # update the value range
105 if total <= 1:
106 min_v = sel_lst[0]
107 max_v = sel_lst[-1]
108 else:
109 min_v = min(min_v, sel_lst[0])
110 max_v = max(max_v, sel_lst[-1])
112 if total <= 0:
113 raise ValueError(
114 "there must be at least one selection, "
115 f"but got {selections}.")
117 # creating super class
118 super().__init__(total, min_v, max_v)
120 #: the selector map
121 self.choices: Final[dict[int, tuple[int, ...]]] = sets
122 #: how often does each element choice appear?
123 self.__counts: Final[dict[tuple[int, ...], int]] = {
124 k: counts[k] for k in sorted(counts.keys())}
125 blueprint.sort()
127 #: The blueprint array, i.e., an ordered array holding the smallest
128 #: value possible for each choice.
129 self.blueprint: Final[np.ndarray] = np.array(
130 blueprint, dtype=self.dtype)
132 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
133 """
134 Log the parameters of this space to the given logger.
136 :param logger: the logger for the parameters
137 """
138 super().log_parameters_to(logger)
140 strings: Final[list[str]] = []
141 for sel, count in self.__counts.items():
142 s = CSV_SEPARATOR.join(map(str, sel))
143 strings.append(s if count <= 1 else (s + "*" + str(count)))
144 logger.key_value(KEY_CHOICES, "/".join(strings))
146 def create(self) -> np.ndarray:
147 r"""
148 Create an ordered choice, equal to :attr:`~OrderedChoices.blueprint`.
150 :return: the ordered choices, an instance of :class:`numpy.ndarray`.
152 >>> perm = OrderedChoices([[1, 3], [2, 4], [1, 3], [7, 5]])
153 >>> x = perm.create()
154 >>> print(perm.to_str(x))
155 1;1;2;5
156 """
157 return self.blueprint.copy() # Create copy of the blueprint.
159 def validate(self, x: np.ndarray) -> None:
160 """
161 Validate a permutation of selections.
163 :param x: the integer string
164 :raises TypeError: if the string is not an :class:`numpy.ndarray`.
165 :raises ValueError: if the element is not a valid permutation of the
166 given choices
167 """
168 super().validate(x)
170 usage: Final[Counter[tuple[int, ...]]] = Counter()
171 dct: Final[dict[int, tuple[int, ...]]] = self.choices
172 for j, i in enumerate(x):
173 if i not in dct:
174 raise ValueError(
175 f"invalid element {i} encountered at index"
176 f" {j} of string {array_to_str(x)}.")
177 usage[dct[i]] += 1
178 counts: Final[dict[tuple[int, ...], int]] = self.__counts
179 for tup, cnt in usage.items():
180 expected = counts[tup]
181 if expected != cnt:
182 raise ValueError(
183 f"encountered value from {tup} exactly {cnt} times "
184 f"instead of the expected {expected} times in {x}")
186 def n_points(self) -> int:
187 """
188 Get the number of possible different permutations of the choices.
190 :return: [factorial(dimension) / Product(factorial(count(e))
191 for all e)] * Product(len(e)*count(e) for all e)
192 """
193 # get the basic permutation numbers now multiply them with the choices
194 size = factorial(self.dimension)
195 for lst, cnt in self.__counts.items():
196 size //= factorial(cnt)
197 size *= len(lst) ** cnt
198 return size
200 def __str__(self) -> str:
201 """
202 Get the name of this space.
204 :return: "selperm{n}", where {n} is the length
205 """
206 return f"selperm{len(self.blueprint)}"
208 def is_compatible_with_permutations(self) -> bool:
209 """
210 Check whether for compatibility with permutations with repetitions.
212 Or, in other words, check whether the operators in package
213 :mod:`~moptipy.operators.permutations` can safely be applied for
214 elements of this space here.
216 Permutations with repetitions are permutations where each element
217 occurs exactly a given number of times. Our implementation of this
218 space (:mod:`~moptipy.spaces.permutations`) ensures that there are
219 at least two different elements. The unary and binary search
220 operators defined in package :mod:`~moptipy.operators.permutations`
221 rely on this fact. While these operators cannot explore the depth
222 of the permutations-of-selections space here, they can be "compatible"
223 to this space: Any element of the permutation-of-selections space is,
224 by definition, a permutation with repetitions, as it contains one
225 concrete manifestation per choice. Applying, for instance, a
226 :mod:`~moptipy.operators.permutations.op1_swap2` operation to it,
227 which swaps two different elements, still yields a valid and different
228 permutation-of-selections. However, since the operators in
229 :mod:`~moptipy.operators.permutations` always enforce that the
230 resulting point is different from their input and *only* permute the
231 elements, this can only work if we have at least two disjoint choices
232 in our space definition. The function here checks this.
234 :returns: `True` if and only if the operators in package
235 :mod:`~moptipy.operators.permutations` can safely be applied to
236 elements of this space
237 """
238 return len(self.__counts) > 1
240 @staticmethod
241 def signed_permutations(n: int) -> "OrderedChoices":
242 """
243 Create a space for signed permutations with values `1..n`.
245 You would be much better off using
246 :mod:`~moptipy.spaces.signed_permutations` instead of this space for
247 signed permutations, though.
249 :param n: the range of the values
250 :returns: the permutations space
252 >>> perm = OrderedChoices.signed_permutations(3)
253 >>> perm.validate(perm.blueprint)
254 >>> print(perm.blueprint)
255 [-3 -2 -1]
256 >>> print(perm.n_points()) # 3! * (2 ** 3) = 6 * 8 = 48
257 48
258 >>> perm = OrderedChoices.signed_permutations(4)
259 >>> perm.validate(perm.blueprint)
260 >>> print(perm.blueprint)
261 [-4 -3 -2 -1]
262 >>> print(perm.n_points()) # 4! * (2 ** 4) = 24 * 16 = 384
263 384
264 """
265 return OrderedChoices([-i, i] for i in range(1, n + 1))