Coverage for moptipy/examples/bitstrings/bitstring

1"""

2A base class for bitstring-based problems.

4Many benchmark problems from discrete optimization are simple functions

5defined over bit strings. We here offer the class :class:`BitStringProblem`,

6which provides reasonable default behavior and several utilities for

7implementing such problems.

8"""

9from itertools import takewhile

10from math import isqrt

11from typing import Callable, Final, Generator, Iterator, cast

13from pycommons.ds.sequences import merge_sorted_and_return_unique

14from pycommons.math.primes import primes

15from pycommons.types import check_int_range

17from moptipy.api.objective import Objective

18from moptipy.spaces.bitstrings import BitStrings

19from moptipy.utils.logger import KeyValueLogSection

22def __powers_of(base: int) -> Generator[int, None, None]:

23 """

24 Yield all powers of the given `base`.

26 :returns: a generator with the powers of `base` greater than 1

28 >>> from itertools import takewhile

29 >>> list(takewhile(lambda x: x < 100, __powers_of(2)))

30 [2, 4, 8, 16, 32, 64]

32 >>> list(takewhile(lambda x: x < 10000, __powers_of(10)))

33 [10, 100, 1000]

34 """

35 pp: int = base

36 while True:

37 yield pp

38 pp *= base

41def __powers_of_2_div_3() -> Generator[int, None, None]:

42 """

43 Yield all powers of 2 // 3 > 2.

45 :returns: a generator with the powers of 2//3 greater than 1

47 >>> from itertools import takewhile

48 >>> list(takewhile(lambda x: x < 100, __powers_of_2_div_3()))

49 [2, 5, 10, 21, 42, 85]

50 """

51 pp: int = 8

52 while True:

53 yield pp // 3

54 pp *= 2

57def __powers_of_2_mul_3() -> Generator[int, None, None]:

58 """

59 Yield all powers of 2 * 3 > 2.

61 :returns: a generator with the powers of 2 * 3 greater than 1

63 >>> from itertools import takewhile

64 >>> list(takewhile(lambda x: x < 100, __powers_of_2_mul_3()))

65 [3, 6, 12, 24, 48, 96]

66 """

67 pp: int = 1

68 while True:

69 yield pp * 3

70 pp *= 2

73def __primes_13() -> Generator[int, None, None]:

74 """

75 Yield a sequence of prime numbers which increase by 1/3.

77 :return: the sequence of prime numbers

79 >>> from itertools import takewhile

80 >>> list(takewhile(lambda x: x < 100, __primes_13()))

81 [2, 3, 5, 7, 11, 17, 23, 31, 41, 59, 79]

82 """

83 last: int = -1

84 for ret in primes():

85 if ((4 * last) // 3) <= ret:

86 yield ret

87 last = ret

90def __1111() -> Generator[int, None, None]:

91 """

92 Yield numbers like 1, 2, ..., 11, 22, 33, ..., 99, 111, 222, 333, ...

94 :returns: yield numbers which are multiples of 1, 11, 111, 1111, etc.

96 >>> from itertools import takewhile

97 >>> list(takewhile(lambda x: x < 10000, __1111()))

98 [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222,\

99 333, 444, 555, 666, 777, 888, 999, 1111, 2222, 3333, 4444, 5555, 6666, 7777,\

100 8888, 9999]

101 """

102 base: int = 1

103 while True:

104 next_base = 10 * base

105 yield from range(base, next_base, base)

106 base = next_base + 1

107

108

109def __1000() -> Generator[int, None, None]:

110 """

111 Yield numbers like 1, 2, ..., 10, 20, 30, ..., 90, 100, 200, 300, ...

112

113 :returns: yield numbers which are multiples of 1, 10, 100, 1000, etc.

114

115 >>> from itertools import takewhile

116 >>> list(takewhile(lambda x: x < 10000, __1000()))

117 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200,\

118 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000, 4000, 5000, 6000,\

119 7000, 8000, 9000]

120 """

121 base: int = 1

122 while True:

123 next_base = 10 * base

124 yield from range(base, next_base, base)

125 base = next_base

126

127

128def default_square_scale_sequence(minimum: int = 2,

129 maximum: int = 3333) -> Iterator[int]:

130 """

131 Get the default sequence of square numbers.

132

133 :param minimum: the smallest permitted value, by default `2`

134 :param maximum: the largest permitted value, by default `3333`

135

136 >>> list(default_square_scale_sequence())

137 [4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, \

138324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, \

1391089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, \

1402025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249]

141

142 >>> list(default_square_scale_sequence(100, 1000))

143 [100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, \

144576, 625, 676, 729, 784, 841, 900, 961]

145

146 >>> try:

147 ... default_square_scale_sequence(-1)

148 ... except ValueError as ve:

149 ... print(ve)

150 minimum=-1 is invalid, must be in 1..1000000000.

151

152 >>> try:

153 ... default_square_scale_sequence("2")

154 ... except TypeError as te:

155 ... print(te)

156 minimum should be an instance of int but is str, namely '2'.

157

158 >>> try:

159 ... default_square_scale_sequence(10, 10)

160 ... except ValueError as ve:

161 ... print(ve)

162 maximum=10 is invalid, must be in 11..1000000000.

163

164 >>> try:

165 ... default_square_scale_sequence(2, "2")

166 ... except TypeError as te:

167 ... print(te)

168 maximum should be an instance of int but is str, namely '2'.

169 """

170 check_int_range(maximum, "maximum", check_int_range(

171 minimum, "minimum", 1, 1_000_000_000) + 1, 1_000_000_000)

172 return (j for j in (i ** 2 for i in range(max(

173 1, isqrt(minimum)), isqrt(maximum) + 1)) if minimum <= j <= maximum)

174

175

176def default_scale_sequence(minimum: int = 2,

177 maximum: int = 3333) -> Iterator[int]:

178 """

179 Get the default scales for investigating discrete optimization.

180

181 :param minimum: the smallest permitted value, by default `2`

182 :param maximum: the largest permitted value, by default `3333`

183

184 >>> list(default_scale_sequence())

185 [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, \

18622, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 36, 40, 41, 42, 44, 48, 49, \

18750, 55, 59, 60, 64, 66, 70, 77, 79, 80, 81, 85, 88, 90, 96, 99, 100, 107, \

188111, 121, 125, 128, 144, 149, 169, 170, 192, 196, 199, 200, 222, 225, 243, \

189256, 269, 289, 300, 324, 333, 341, 343, 359, 361, 384, 400, 441, 444, 479, \

190484, 500, 512, 529, 555, 576, 600, 625, 641, 666, 676, 682, 700, 729, 768, \

191777, 784, 800, 841, 857, 888, 900, 961, 999, 1000, 1024, 1089, 1111, 1151, \

1921156, 1225, 1296, 1365, 1369, 1444, 1521, 1536, 1543, 1600, 1681, 1764, \

1931849, 1936, 2000, 2025, 2048, 2063, 2116, 2187, 2209, 2222, 2304, 2401, \

1942500, 2601, 2704, 2730, 2753, 2809, 2916, 3000, 3025, 3072, 3125, 3136, \

1953249, 3333]

196

197 >>> list(default_scale_sequence(10, 100))

198 [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, \

19928, 29, 30, 31, 32, 33, 36, 40, 41, 42, 44, 48, 49, 50, 55, 59, 60, 64, 66, \

20070, 77, 79, 80, 81, 85, 88, 90, 96, 99, 100]

201

202 >>> list(default_scale_sequence(maximum=100))

203 [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, \

20422, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 36, 40, 41, 42, 44, 48, 49, \

20550, 55, 59, 60, 64, 66, 70, 77, 79, 80, 81, 85, 88, 90, 96, 99, 100]

206

207 >>> list(default_scale_sequence(9000, 10000))

208 [9000, 9025, 9216, 9409, 9604, 9801, 9999, 10000]

209

210 >>> try:

211 ... default_scale_sequence(-1)

212 ... except ValueError as ve:

213 ... print(ve)

214 minimum=-1 is invalid, must be in 1..1000000000.

215

216 >>> try:

217 ... default_scale_sequence("2")

218 ... except TypeError as te:

219 ... print(te)

220 minimum should be an instance of int but is str, namely '2'.

221

222 >>> try:

223 ... default_scale_sequence(10, 10)

224 ... except ValueError as ve:

225 ... print(ve)

226 maximum=10 is invalid, must be in 11..1000000000.

227

228 >>> try:

229 ... default_scale_sequence(2, "2")

230 ... except TypeError as te:

231 ... print(te)

232 maximum should be an instance of int but is str, namely '2'.

233 """

234 check_int_range(maximum, "maximum", check_int_range(

235 minimum, "minimum", 1, 1_000_000_000) + 1, 1_000_000_000)

236 return filter(

237 lambda x: minimum <= x <= maximum, takewhile(

238 lambda x: x <= maximum, merge_sorted_and_return_unique(

239 __powers_of(2), __powers_of(3), __powers_of(5), __powers_of(7),

240 __powers_of(10), __powers_of_2_div_3(), __powers_of_2_mul_3(),

241 __primes_13(), __1111(), __1000(), range(32), (625, ),

242 default_square_scale_sequence(minimum, maximum))))

243

244

245class BitStringProblem(Objective):

246 """

247 A base class for problems defined over bit strings.

248

249 This base class has a set of default behaviors. It has an attribute

250 :attr:`n` denoting the lengths of the accepted bit strings. Its

251 :meth:`lower_bound` returns `0` and its :meth:`upper_bound` returns

252 :attr:`n`. :meth:`is_always_integer` returns `True`. If also offers

253 the method :meth:`space` which returns an instance of

254 :class:`~moptipy.spaces.bitstrings.BitStrings` for bit strings of

255 length :attr:`n`.

256

257 >>> bs = BitStringProblem(1)

258 >>> bs.n

259 1

260

261 >>> try:

262 ... bs = BitStringProblem(0)

263 ... except ValueError as ve:

264 ... print(ve)

265 n=0 is invalid, must be in 1..1000000000.

266

267 >>> try:

268 ... bs = BitStringProblem("a")

269 ... except TypeError as te:

270 ... print(te)

271 n should be an instance of int but is str, namely 'a'.

272 """

273

274 def __init__(self, n: int) -> None:

275 """

276 Initialize the bitstring objective function.

277

278 :param n: the dimension of the problem

279 """

280 super().__init__()

281 #: the length of the bit strings

282 self.n: Final[int] = check_int_range(n, "n", 1)

283

284 def lower_bound(self) -> int:

285 """

286 Get the lower bound of the bit string based problem.

287

288 By default, this method returns `0`. Problems where the lower bound

289 differs should override this method.

290

291 :return: 0

292

293 >>> print(BitStringProblem(10).lower_bound())

294 0

295 """

296 return 0

297

298 def upper_bound(self) -> int:

299 """

300 Get the upper bound of the bit string based problem.

301

302 The default value is the length of the bit string. Problems where the

303 upper bound differs should overrrite this method.

304

305 :return: by default, this is the length of the bit string

306

307 >>> print(BitStringProblem(7).upper_bound())

308 7

309 """

310 return self.n

311

312 def is_always_integer(self) -> bool:

313 """

314 Return `True` if the `evaluate` function always returns an `int`.

315

316 This pre-defined function for bit-string based problems will always

317 return `True`. Problems where this is not the case should overwrite

318 this method.

319

320 :retval True: always

321 """

322 return True

323

324 def space(self) -> BitStrings:

325 """

326 Create a proper search space for this problem.

327

328 :returns: an instance of

329 :class:`~moptipy.spaces.bitstrings.BitStrings` for bit strings of

330 length :attr:`n`

331 """

332 return BitStrings(self.n)

333

334 def log_parameters_to(self, logger: KeyValueLogSection) -> None:

335 """

336 Log all parameters of this component as key-value pairs.

337

338 :param logger: the logger for the parameters

339

340 >>> from moptipy.utils.logger import InMemoryLogger

341 >>> with InMemoryLogger() as l:

342 ... with l.key_values("C") as kv:

343 ... BitStringProblem(5).log_parameters_to(kv)

344 ... text = l.get_log()

345 >>> text[1]

346 'name: bitstringproblem_5'

347 >>> text[3]

348 'lowerBound: 0'

349 >>> text[4]

350 'upperBound: 5'

351 >>> text[5]

352 'n: 5'

353 >>> len(text)

354 7

355 """

356 super().log_parameters_to(logger)

357 logger.key_value("n", self.n)

358

359 def __str__(self) -> str:

360 """

361 Get the name of the problem.

362

363 :returns: the name of the problem, which by default is the class name

364 in lower case, followed by an underscore and the number of bits

365 """

366 return f"{super().__str__().lower()}_{self.n}"

367

368 @classmethod

369 def default_instances(

370 cls: type, scale_min: int = 2, scale_max: int = 3333) \

371 -> Iterator[Callable[[], "BitStringProblem"]]:

372 """

373 Get the default instances of this problem type.

374

375 :param scale_min: the minimum scale

376 :param scale_max: the maximum scale

377 :return: an :class:`Iterator` with the instances

378 """

379 return (cast("Callable[[], BitStringProblem]",

380 lambda __i=i: cls(__i)) for i in default_scale_sequence(

381 scale_min, scale_max))

382

383

384class SquareBitStringProblem(BitStringProblem):

385 """

386 A bitstring problem which requires that the string length is square.

387

388 >>> sb = SquareBitStringProblem(9)

389 >>> sb.n

390 9

391 >>> sb.k

392 3

393

394 >>> try:

395 ... bs = SquareBitStringProblem(0)

396 ... except ValueError as ve:

397 ... print(ve)

398 n=0 is invalid, must be in 4..1000000000.

399

400 >>> try:

401 ... bs = SquareBitStringProblem(3)

402 ... except ValueError as ve:

403 ... print(ve)

404 n=3 is invalid, must be in 4..1000000000.

405

406 >>> try:

407 ... bs = SquareBitStringProblem(21)

408 ... except ValueError as ve:

409 ... print(ve)

410 n=21 must be a square number, but isqrt(n)=4 does not satisfy n = k*k.

411

412 >>> try:

413 ... bs = SquareBitStringProblem("a")

414 ... except TypeError as te:

415 ... print(te)

416 n should be an instance of int but is str, namely 'a'.

417 """

418

419 def __init__(self, n: int) -> None:

420 """

421 Initialize the square bitstring problem.

422

423 :param n: the dimension of the problem (must be a perfect square)

424 """

425 super().__init__(check_int_range(n, "n", 4))

426 k: Final[int] = check_int_range(isqrt(n), "k", 2)

427 if (k * k) != n:

428 raise ValueError(f"n={n} must be a square number, but"

429 f" isqrt(n)={k} does not satisfy n = k*k.")

430 #: the k value, i.e., the number of bits per row and column of

431 #: the square

432 self.k: Final[int] = k

433

434 def log_parameters_to(self, logger: KeyValueLogSection) -> None:

435 """

436 Log all parameters of this component as key-value pairs.

437

438 :param logger: the logger for the parameters

439

440 >>> from moptipy.utils.logger import InMemoryLogger

441 >>> with InMemoryLogger() as l:

442 ... with l.key_values("C") as kv:

443 ... SquareBitStringProblem(49).log_parameters_to(kv)

444 ... text = l.get_log()

445 >>> text[1]

446 'name: squarebitstringproblem_49'

447 >>> text[3]

448 'lowerBound: 0'

449 >>> text[4]

450 'upperBound: 49'

451 >>> text[5]

452 'n: 49'

453 >>> text[6]

454 'k: 7'

455 >>> len(text)

456 8

457 """

458 super().log_parameters_to(logger)

459 logger.key_value("k", self.k)

460

461 @classmethod

462 def default_instances(

463 cls: type, scale_min: int = 4, scale_max: int = 3333) \

464 -> Iterator[Callable[[], "SquareBitStringProblem"]]:

465 """

466 Get the default instances of this problem type.

467

468 :return: an :class:`Iterator` with the instances

469 """

470 return (cast("Callable[[], SquareBitStringProblem]",

471 lambda __i=i: cls(__i))

472 for i in default_square_scale_sequence(scale_min, scale_max))

473

474

475def default_nk_k_sequence(n: int) -> Iterator[int]:

476 """

477 Get the default values of `k` for a :class:`BitStringNKProblem`.

478

479 :param n: the `n` value for the :class:`BitStringNKProblem`.

480 :return: a sequence of appropriate `k` values

481

482 >>> list(default_nk_k_sequence(6))

483 [2]

484

485 >>> list(default_nk_k_sequence(7))

486 [2]

487

488 >>> list(default_nk_k_sequence(8))

489 [2, 3]

490

491 >>> list(default_nk_k_sequence(10))

492 [2, 3, 4]

493

494 >>> list(default_nk_k_sequence(20))

495 [2, 3, 4, 5, 7, 9]

496

497 >>> list(default_nk_k_sequence(32))

498 [2, 4, 5, 8, 11, 15]

499

500 >>> try:

501 ... default_nk_k_sequence(3)

502 ... except ValueError as ve:

503 ... print(ve)

504 n=3 is invalid, must be in 6..1000000000.

505

506 >>> try:

507 ... default_nk_k_sequence("6")

508 ... except TypeError as te:

509 ... print(te)

510 n should be an instance of int but is str, namely '6'.

511 """

512 check_int_range(n, "n", 6)

513 nhalf: Final[int] = n // 2

514 ofs: Final[int] = nhalf - 2

515 base: Final[set[int]] = {1 + (j * ofs) // 4 for j in range(5)}

516 base.add(2)

517 base.add(nhalf - 1)

518 base.add(isqrt(n))

519 return (i for i in sorted(base) if 1 < i < nhalf)

520

521

522class BitStringNKProblem(BitStringProblem):

523 """

524 A bit string problem with a second parameter `k` with `1 < k < n/2`.

525

526 >>> sb = BitStringNKProblem(9, 3)

527 >>> sb.n

528 9

529 >>> sb.k

530 3

531

532 >>> try:

533 ... bs = BitStringNKProblem(0, 3)

534 ... except ValueError as ve:

535 ... print(ve)

536 n=0 is invalid, must be in 6..1000000000.

537

538 >>> try:

539 ... bs = BitStringNKProblem(5, 2)

540 ... except ValueError as ve:

541 ... print(ve)

542 n=5 is invalid, must be in 6..1000000000.

543

544 >>> try:

545 ... bs = BitStringNKProblem(21, 20)

546 ... except ValueError as ve:

547 ... print(ve)

548 k=20 is invalid, must be in 2..9.

549

550 >>> try:

551 ... bs = BitStringNKProblem("a", 3)

552 ... except TypeError as te:

553 ... print(te)

554 n should be an instance of int but is str, namely 'a'.

555

556 >>> try:

557 ... bs = BitStringNKProblem(13, "x")

558 ... except TypeError as te:

559 ... print(te)

560 k should be an instance of int but is str, namely 'x'.

561 """

562

563 def __init__(self, n: int, k: int) -> None:

564 """

565 Initialize the n-k objective function.

566

567 :param n: the dimension of the problem

568 :param k: the second parameter

569 """

570 super().__init__(check_int_range(n, "n", 6))

571 #: the second parameter, with `1 < k < n/2`

572 self.k: Final[int] = check_int_range(k, "k", 2, (n >> 1) - 1)

573

574 def __str__(self) -> str:

575 """

576 Get the name of the objective function.

577

578 :return: `class_` + length of string + `_` + k

579

580 >>> BitStringNKProblem(13, 4)

581 bitstringnkproblem_13_4

582 """

583 return f"{super().__str__()}_{self.k}"

584

585 def log_parameters_to(self, logger: KeyValueLogSection) -> None:

586 """

587 Log all parameters of this component as key-value pairs.

588

589 :param logger: the logger for the parameters

590

591 >>> from moptipy.utils.logger import InMemoryLogger

592 >>> with InMemoryLogger() as l:

593 ... with l.key_values("C") as kv:

594 ... BitStringNKProblem(23, 7).log_parameters_to(kv)

595 ... text = l.get_log()

596 >>> text[1]

597 'name: bitstringnkproblem_23_7'

598 >>> text[3]

599 'lowerBound: 0'

600 >>> text[4]

601 'upperBound: 23'

602 >>> text[5]

603 'n: 23'

604 >>> text[6]

605 'k: 7'

606 >>> len(text)

607 8

608 """

609 super().log_parameters_to(logger)

610 logger.key_value("k", self.k)

611

612 @classmethod

613 def default_instances(

614 cls: type, scale_min: int = 6, scale_max: int = 32) \

615 -> Iterator[Callable[[], "BitStringNKProblem"]]:

616 """

617 Get the default instances of this problem type.

618

619 :return: an :class:`Iterator` with the instances

620 """

621 return (cast("Callable[[], BitStringNKProblem]",

622 lambda __i=i, __j=j: cls(__i, __j))

623 for i in default_scale_sequence(scale_min, scale_max)

624 for j in default_nk_k_sequence(i))

Coverage for moptipy / examples / bitstrings / bitstring_problem.py: 100%

102 statements