Coverage for moptipy/examples/bitstrings/leadingones.py: 75%

1"""

2An objective function counting the leading ones in a bit string.

4LeadingOnes is a standard benchmark problem in evolutionary computation.

5It attempts to maximize the number of consecutive True bits at the beginning

6of a bit string. Its best possible objective value is 0, the worst possible

7is `n`.

91. L. Darrell Whitley. The GENITOR Algorithm and Selection Pressure: Why

10 Rank-Based Allocation of Reproductive Trials is Best. In J. David Schaffer,

11 ed., Proceedings of the 3rd International Conference on Genetic Algorithms

12 (ICGA'89), June 4-7, 1989, Fairfax, VA, USA, pages 116-121. San Francisco,

13 CA, USA: Morgan Kaufmann Publishers Inc. ISBN: 1-55860-066-3

14 https://www.researchgate.net/publication/2527551

152. Günter Rudolph, Convergence Properties of Evolutionary Algorithms. Hamburg,

16 Germany: Verlag Dr. Kovač, 1997.

173. Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Kasper Green Larsen,

18 Kurt Mehlhorn, and Carola Winzen. The Query Complexity of Finding a Hidden

19 Permutation. Space-Efficient Data Structures, Streams, and Algorithms.

20 pp. 1-11. Springer. 2013.

21 doi: https://doi.org/10.1007/978-3-642-40273-9_1

224. Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper

23 Green Larsen, Kurt Mehlhorn. The Query Complexity of a Permutation-Based

24 Variant of Mastermind. Discrete Applied Mathematics. 260:28-50. 2019.

25 doi: https://doi.org/10.1016/j.dam.2019.01.007

265. Stefan Droste, Thomas Jansen, and Ingo Wegener. On the Analysis of the

27 (1+1) Evolutionary Algorithm. Theoretical Computer Science.

28 276(1-2):51-81. 2002.

29 doi: https://doi.org/10.1016/S0304-3975(01)00182-7.

306. Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. A Tight Runtime

31 Analysis for the (1+(λ,λ)) GA on LeadingOnes. FOGA 2019, pp. 169-182. ACM.

32 doi: https://doi.org/10.1145/3299904.3340317.

337. Vitalii Karavaev, Denis Antipov, and Benjamin Doerr. Theoretical and

34 Empirical Study of the (1+(λ,λ)) EA on the LeadingOnes Problem. GECCO

35 (Companion) 2019. pp 2036-2039. ACM.

36 doi: https://doi.org/10.1145/3319619.3326910.

378. Thomas Weise, Zhize Wu, Xinlu Li, and Yan Chen. Frequency Fitness

38 Assignment: Making Optimization Algorithms Invariant under Bijective

39 Transformations of the Objective Function Value. *IEEE Transactions on

40 Evolutionary Computation* 25(2):307-319. April 2021. Preprint available at

41 arXiv:2001.01416v5 [cs.NE] 15 Oct 2020.

42 https://dx.doi.org/10.1109/TEVC.2020.3032090

439. Thomas Weise, Zhize Wu, Xinlu Li, Yan Chen, and Jörg Lässig. Frequency

44 Fitness Assignment: Optimization without Bias for Good Solutions can be

45 Efficient. *IEEE Transactions on Evolutionary Computation (TEVC)*.

46 27(4):980-992. August 2023.

47 doi: https://doi.org/10.1109/TEVC.2022.3191698

48"""

49from typing import Callable, Final, Iterator, cast

51import numba # type: ignore

52import numpy as np

54from moptipy.examples.bitstrings.bitstring_problem import BitStringProblem

57@numba.njit(nogil=True, cache=True)

58def leadingones(x: np.ndarray) -> int:

59 """

60 Get the length of the string minus the number of leading ones.

62 :param x: the np array

63 :return: the number of leading ones

65 >>> leadingones(np.array([False, False, True, False, False]))

66 5

67 >>> leadingones(np.array([True, False, False, True, True]))

68 4

69 >>> leadingones(np.array([True, True, False, False, False]))

70 3

71 >>> leadingones(np.array([True, True, True, False, True]))

72 2

73 >>> leadingones(np.array([True, True, True, True, False]))

74 1

75 >>> leadingones(np.array([True, True, True, True, True]))

76 0

78 # n = 1 and 0 true bits

79 >>> leadingones(np.array([0]))

80 1

82 # n = 1 and 1 true bit

83 >>> leadingones(np.array([1]))

84 0

86 # n = 2 and 0 true bits

87 >>> leadingones(np.array([0, 0]))

88 2

90 # n = 2 and 1 true bit

91 >>> leadingones(np.array([1, 0]))

92 1

94 # n = 2 and 1 true bit

95 >>> leadingones(np.array([0, 1]))

96 2

98 # n = 2 and 1 true bit

99 >>> leadingones(np.array([1, 0]))

100 1

101

102 # n = 2 and 2 true bits

103 >>> leadingones(np.array([1, 1]))

104 0

105

106 # n = 3 and 0 true bits

107 >>> leadingones(np.array([0, 0, 0]))

108 3

109

110 # n = 3 and 1 true bit

111 >>> leadingones(np.array([0, 1, 0]))

112 3

113

114 # n = 3 and 1 true bit

115 >>> leadingones(np.array([0, 0, 1]))

116 3

117

118 # n = 3 and 1 true bit

119 >>> leadingones(np.array([0, 1, 0]))

120 3

121

122 # n = 3 and 2 true bits

123 >>> leadingones(np.array([1, 1, 0]))

124 1

125

126 # n = 3 and 2 true bits

127 >>> leadingones(np.array([1, 0, 1]))

128 2

129

130 # n = 3 and 2 true bits

131 >>> leadingones(np.array([1, 1, 0]))

132 1

133

134 # n = 3 and 3 true bits

135 >>> leadingones(np.array([1, 1, 1]))

136 0

137

138 # n = 4 and 0 true bits

139 >>> leadingones(np.array([0, 0, 0, 0]))

140 4

141

142 # n = 4 and 1 true bit

143 >>> leadingones(np.array([1, 0, 0, 0]))

144 3

145

146 # n = 4 and 1 true bit

147 >>> leadingones(np.array([0, 0, 1, 0]))

148 4

149

150 # n = 4 and 1 true bit

151 >>> leadingones(np.array([1, 0, 0, 0]))

152 3

153

154 # n = 4 and 2 true bits

155 >>> leadingones(np.array([1, 0, 0, 1]))

156 3

157

158 # n = 4 and 2 true bits

159 >>> leadingones(np.array([0, 1, 0, 1]))

160 4

161

162 # n = 4 and 2 true bits

163 >>> leadingones(np.array([0, 1, 1, 0]))

164 4

165

166 # n = 4 and 3 true bits

167 >>> leadingones(np.array([1, 1, 1, 0]))

168 1

169

170 # n = 4 and 3 true bits

171 >>> leadingones(np.array([1, 1, 1, 0]))

172 1

173

174 # n = 4 and 3 true bits

175 >>> leadingones(np.array([0, 1, 1, 1]))

176 4

177

178 # n = 4 and 4 true bits

179 >>> leadingones(np.array([1, 1, 1, 1]))

180 0

181

182 # n = 5 and 0 true bits

183 >>> leadingones(np.array([0, 0, 0, 0, 0]))

184 5

185

186 # n = 5 and 1 true bit

187 >>> leadingones(np.array([0, 1, 0, 0, 0]))

188 5

189

190 # n = 5 and 1 true bit

191 >>> leadingones(np.array([0, 1, 0, 0, 0]))

192 5

193

194 # n = 5 and 1 true bit

195 >>> leadingones(np.array([0, 1, 0, 0, 0]))

196 5

197

198 # n = 5 and 2 true bits

199 >>> leadingones(np.array([1, 1, 0, 0, 0]))

200 3

201

202 # n = 5 and 2 true bits

203 >>> leadingones(np.array([1, 0, 0, 1, 0]))

204 4

205

206 # n = 5 and 2 true bits

207 >>> leadingones(np.array([0, 0, 1, 1, 0]))

208 5

209

210 # n = 5 and 3 true bits

211 >>> leadingones(np.array([1, 0, 0, 1, 1]))

212 4

213

214 # n = 5 and 3 true bits

215 >>> leadingones(np.array([1, 1, 1, 0, 0]))

216 2

217

218 # n = 5 and 3 true bits

219 >>> leadingones(np.array([0, 0, 1, 1, 1]))

220 5

221

222 # n = 5 and 4 true bits

223 >>> leadingones(np.array([1, 1, 0, 1, 1]))

224 3

225

226 # n = 5 and 4 true bits

227 >>> leadingones(np.array([1, 1, 0, 1, 1]))

228 3

229

230 # n = 5 and 4 true bits

231 >>> leadingones(np.array([1, 1, 1, 1, 0]))

232 1

233

234 # n = 5 and 5 true bits

235 >>> leadingones(np.array([1, 1, 1, 1, 1]))

236 0

237

238 # n = 6 and 0 true bits

239 >>> leadingones(np.array([0, 0, 0, 0, 0, 0]))

240 6

241

242 # n = 6 and 1 true bit

243 >>> leadingones(np.array([0, 0, 1, 0, 0, 0]))

244 6

245

246 # n = 6 and 1 true bit

247 >>> leadingones(np.array([0, 1, 0, 0, 0, 0]))

248 6

249

250 # n = 6 and 1 true bit

251 >>> leadingones(np.array([1, 0, 0, 0, 0, 0]))

252 5

253

254 # n = 6 and 2 true bits

255 >>> leadingones(np.array([0, 1, 0, 0, 0, 1]))

256 6

257

258 # n = 6 and 2 true bits

259 >>> leadingones(np.array([0, 0, 1, 0, 0, 1]))

260 6

261

262 # n = 6 and 2 true bits

263 >>> leadingones(np.array([0, 0, 1, 0, 1, 0]))

264 6

265

266 # n = 6 and 3 true bits

267 >>> leadingones(np.array([0, 1, 0, 1, 1, 0]))

268 6

269

270 # n = 6 and 3 true bits

271 >>> leadingones(np.array([1, 0, 0, 0, 1, 1]))

272 5

273

274 # n = 6 and 3 true bits

275 >>> leadingones(np.array([0, 0, 1, 1, 1, 0]))

276 6

277

278 # n = 6 and 4 true bits

279 >>> leadingones(np.array([0, 1, 0, 1, 1, 1]))

280 6

281

282 # n = 6 and 4 true bits

283 >>> leadingones(np.array([0, 1, 1, 1, 1, 0]))

284 6

285

286 # n = 6 and 4 true bits

287 >>> leadingones(np.array([0, 1, 1, 0, 1, 1]))

288 6

289

290 # n = 6 and 5 true bits

291 >>> leadingones(np.array([1, 0, 1, 1, 1, 1]))

292 5

293

294 # n = 6 and 5 true bits

295 >>> leadingones(np.array([1, 1, 1, 1, 1, 0]))

296 1

297

298 # n = 6 and 5 true bits

299 >>> leadingones(np.array([1, 0, 1, 1, 1, 1]))

300 5

301

302 # n = 6 and 6 true bits

303 >>> leadingones(np.array([1, 1, 1, 1, 1, 1]))

304 0

305

306 # n = 7 and 0 true bits

307 >>> leadingones(np.array([0, 0, 0, 0, 0, 0, 0]))

308 7

309

310 # n = 7 and 1 true bit

311 >>> leadingones(np.array([0, 0, 0, 0, 0, 0, 1]))

312 7

313

314 # n = 7 and 1 true bit

315 >>> leadingones(np.array([0, 0, 0, 0, 1, 0, 0]))

316 7

317

318 # n = 7 and 1 true bit

319 >>> leadingones(np.array([0, 0, 1, 0, 0, 0, 0]))

320 7

321

322 # n = 7 and 2 true bits

323 >>> leadingones(np.array([0, 1, 0, 0, 0, 1, 0]))

324 7

325

326 # n = 7 and 2 true bits

327 >>> leadingones(np.array([0, 0, 1, 0, 0, 1, 0]))

328 7

329

330 # n = 7 and 2 true bits

331 >>> leadingones(np.array([0, 0, 0, 1, 0, 1, 0]))

332 7

333

334 # n = 7 and 3 true bits

335 >>> leadingones(np.array([1, 0, 0, 0, 0, 1, 1]))

336 6

337

338 # n = 7 and 3 true bits

339 >>> leadingones(np.array([1, 0, 1, 0, 0, 1, 0]))

340 6

341

342 # n = 7 and 3 true bits

343 >>> leadingones(np.array([1, 0, 0, 1, 1, 0, 0]))

344 6

345

346 # n = 7 and 4 true bits

347 >>> leadingones(np.array([1, 0, 0, 1, 1, 1, 0]))

348 6

349

350 # n = 7 and 4 true bits

351 >>> leadingones(np.array([1, 0, 1, 1, 0, 1, 0]))

352 6

353

354 # n = 7 and 4 true bits

355 >>> leadingones(np.array([1, 1, 1, 0, 1, 0, 0]))

356 4

357

358 # n = 7 and 5 true bits

359 >>> leadingones(np.array([0, 1, 1, 1, 0, 1, 1]))

360 7

361

362 # n = 7 and 5 true bits

363 >>> leadingones(np.array([1, 1, 0, 0, 1, 1, 1]))

364 5

365

366 # n = 7 and 5 true bits

367 >>> leadingones(np.array([0, 1, 1, 1, 1, 0, 1]))

368 7

369

370 # n = 7 and 6 true bits

371 >>> leadingones(np.array([1, 1, 0, 1, 1, 1, 1]))

372 5

373

374 # n = 7 and 6 true bits

375 >>> leadingones(np.array([1, 1, 1, 1, 0, 1, 1]))

376 3

377

378 # n = 7 and 6 true bits

379 >>> leadingones(np.array([1, 1, 0, 1, 1, 1, 1]))

380 5

381

382 # n = 7 and 7 true bits

383 >>> leadingones(np.array([1, 1, 1, 1, 1, 1, 1]))

384 0

385

386 # n = 8 and 0 true bits

387 >>> leadingones(np.array([0, 0, 0, 0, 0, 0, 0, 0]))

388 8

389

390 # n = 8 and 1 true bit

391 >>> leadingones(np.array([0, 0, 0, 0, 0, 1, 0, 0]))

392 8

393

394 # n = 8 and 1 true bit

395 >>> leadingones(np.array([0, 0, 0, 0, 1, 0, 0, 0]))

396 8

397

398 # n = 8 and 1 true bit

399 >>> leadingones(np.array([1, 0, 0, 0, 0, 0, 0, 0]))

400 7

401

402 # n = 8 and 2 true bits

403 >>> leadingones(np.array([0, 0, 0, 1, 0, 0, 0, 1]))

404 8

405

406 # n = 8 and 2 true bits

407 >>> leadingones(np.array([0, 1, 0, 0, 0, 0, 0, 1]))

408 8

409

410 # n = 8 and 2 true bits

411 >>> leadingones(np.array([0, 1, 0, 1, 0, 0, 0, 0]))

412 8

413

414 # n = 8 and 3 true bits

415 >>> leadingones(np.array([1, 0, 0, 0, 1, 0, 1, 0]))

416 7

417

418 # n = 8 and 3 true bits

419 >>> leadingones(np.array([1, 0, 1, 0, 1, 0, 0, 0]))

420 7

421

422 # n = 8 and 3 true bits

423 >>> leadingones(np.array([0, 0, 0, 1, 0, 0, 1, 1]))

424 8

425

426 # n = 8 and 4 true bits

427 >>> leadingones(np.array([1, 1, 0, 0, 0, 0, 1, 1]))

428 6

429

430 # n = 8 and 4 true bits

431 >>> leadingones(np.array([1, 1, 0, 1, 0, 1, 0, 0]))

432 6

433

434 # n = 8 and 4 true bits

435 >>> leadingones(np.array([0, 0, 1, 0, 1, 1, 1, 0]))

436 8

437

438 # n = 8 and 5 true bits

439 >>> leadingones(np.array([1, 1, 1, 1, 0, 0, 1, 0]))

440 4

441

442 # n = 8 and 5 true bits

443 >>> leadingones(np.array([1, 0, 1, 1, 0, 0, 1, 1]))

444 7

445

446 # n = 8 and 5 true bits

447 >>> leadingones(np.array([0, 1, 0, 1, 1, 1, 0, 1]))

448 8

449

450 # n = 8 and 6 true bits

451 >>> leadingones(np.array([1, 1, 1, 1, 0, 1, 0, 1]))

452 4

453

454 # n = 8 and 6 true bits

455 >>> leadingones(np.array([1, 1, 0, 1, 1, 1, 0, 1]))

456 6

457

458 # n = 8 and 6 true bits

459 >>> leadingones(np.array([1, 1, 0, 1, 1, 1, 0, 1]))

460 6

461

462 # n = 8 and 7 true bits

463 >>> leadingones(np.array([0, 1, 1, 1, 1, 1, 1, 1]))

464 8

465

466 # n = 8 and 7 true bits

467 >>> leadingones(np.array([1, 1, 0, 1, 1, 1, 1, 1]))

468 6

469

470 # n = 8 and 7 true bits

471 >>> leadingones(np.array([1, 1, 1, 1, 1, 0, 1, 1]))

472 3

473

474 # n = 8 and 8 true bits

475 >>> leadingones(np.array([1, 1, 1, 1, 1, 1, 1, 1]))

476 0

477

478 # n = 9 and 0 true bits

479 >>> leadingones(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0]))

480 9

481

482 # n = 9 and 1 true bit

483 >>> leadingones(np.array([0, 0, 0, 0, 0, 1, 0, 0, 0]))

484 9

485

486 # n = 9 and 1 true bit

487 >>> leadingones(np.array([0, 0, 0, 0, 1, 0, 0, 0, 0]))

488 9

489

490 # n = 9 and 1 true bit

491 >>> leadingones(np.array([0, 0, 1, 0, 0, 0, 0, 0, 0]))

492 9

493

494 # n = 9 and 2 true bits

495 >>> leadingones(np.array([0, 0, 0, 0, 0, 1, 0, 0, 1]))

496 9

497

498 # n = 9 and 2 true bits

499 >>> leadingones(np.array([0, 0, 0, 0, 1, 1, 0, 0, 0]))

500 9

501

502 # n = 9 and 2 true bits

503 >>> leadingones(np.array([1, 0, 0, 0, 0, 0, 1, 0, 0]))

504 8

505

506 # n = 9 and 3 true bits

507 >>> leadingones(np.array([0, 1, 0, 0, 1, 0, 0, 0, 1]))

508 9

509

510 # n = 9 and 3 true bits

511 >>> leadingones(np.array([0, 1, 1, 0, 0, 1, 0, 0, 0]))

512 9

513

514 # n = 9 and 3 true bits

515 >>> leadingones(np.array([0, 1, 1, 0, 0, 0, 0, 0, 1]))

516 9

517

518 # n = 9 and 4 true bits

519 >>> leadingones(np.array([0, 1, 0, 0, 1, 0, 0, 1, 1]))

520 9

521

522 # n = 9 and 4 true bits

523 >>> leadingones(np.array([1, 1, 0, 0, 1, 0, 0, 1, 0]))

524 7

525

526 # n = 9 and 4 true bits

527 >>> leadingones(np.array([0, 1, 1, 1, 0, 0, 1, 0, 0]))

528 9

529

530 # n = 9 and 5 true bits

531 >>> leadingones(np.array([0, 0, 1, 1, 1, 1, 0, 1, 0]))

532 9

533

534 # n = 9 and 5 true bits

535 >>> leadingones(np.array([0, 0, 1, 1, 1, 0, 0, 1, 1]))

536 9

537

538 # n = 9 and 5 true bits

539 >>> leadingones(np.array([1, 0, 0, 1, 1, 0, 0, 1, 1]))

540 8

541

542 # n = 9 and 6 true bits

543 >>> leadingones(np.array([1, 1, 1, 0, 1, 1, 0, 0, 1]))

544 6

545

546 # n = 9 and 6 true bits

547 >>> leadingones(np.array([1, 0, 1, 1, 1, 1, 1, 0, 0]))

548 8

549

550 # n = 9 and 6 true bits

551 >>> leadingones(np.array([1, 1, 0, 1, 1, 1, 0, 0, 1]))

552 7

553

554 # n = 9 and 7 true bits

555 >>> leadingones(np.array([1, 1, 0, 1, 0, 1, 1, 1, 1]))

556 7

557

558 # n = 9 and 7 true bits

559 >>> leadingones(np.array([1, 0, 1, 1, 1, 1, 0, 1, 1]))

560 8

561

562 # n = 9 and 7 true bits

563 >>> leadingones(np.array([1, 0, 1, 1, 1, 0, 1, 1, 1]))

564 8

565

566 # n = 9 and 8 true bits

567 >>> leadingones(np.array([1, 1, 1, 0, 1, 1, 1, 1, 1]))

568 6

569

570 # n = 9 and 8 true bits

571 >>> leadingones(np.array([1, 0, 1, 1, 1, 1, 1, 1, 1]))

572 8

573

574 # n = 9 and 8 true bits

575 >>> leadingones(np.array([1, 0, 1, 1, 1, 1, 1, 1, 1]))

576 8

577

578 # n = 9 and 9 true bits

579 >>> leadingones(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1]))

580 0

581

582 # n = 10 and 0 true bits

583 >>> leadingones(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]))

584 10

585

586 # n = 10 and 1 true bit

587 >>> leadingones(np.array([0, 0, 0, 0, 1, 0, 0, 0, 0, 0]))

588 10

589

590 # n = 10 and 1 true bit

591 >>> leadingones(np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0]))

592 9

593

594 # n = 10 and 1 true bit

595 >>> leadingones(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 1]))

596 10

597

598 # n = 10 and 2 true bits

599 >>> leadingones(np.array([0, 1, 1, 0, 0, 0, 0, 0, 0, 0]))

600 10

601

602 # n = 10 and 2 true bits

603 >>> leadingones(np.array([0, 0, 1, 1, 0, 0, 0, 0, 0, 0]))

604 10

605

606 # n = 10 and 2 true bits

607 >>> leadingones(np.array([0, 0, 0, 0, 0, 0, 0, 0, 1, 1]))

608 10

609

610 # n = 10 and 3 true bits

611 >>> leadingones(np.array([0, 1, 0, 1, 0, 0, 0, 1, 0, 0]))

612 10

613

614 # n = 10 and 3 true bits

615 >>> leadingones(np.array([1, 0, 0, 0, 1, 0, 0, 1, 0, 0]))

616 9

617

618 # n = 10 and 3 true bits

619 >>> leadingones(np.array([0, 1, 0, 0, 0, 1, 0, 0, 0, 1]))

620 10

621

622 # n = 10 and 4 true bits

623 >>> leadingones(np.array([1, 1, 0, 0, 0, 1, 0, 0, 1, 0]))

624 8

625

626 # n = 10 and 4 true bits

627 >>> leadingones(np.array([1, 0, 0, 1, 0, 1, 1, 0, 0, 0]))

628 9

629

630 # n = 10 and 4 true bits

631 >>> leadingones(np.array([1, 0, 0, 0, 1, 1, 0, 0, 0, 1]))

632 9

633

634 # n = 10 and 5 true bits

635 >>> leadingones(np.array([0, 0, 0, 1, 1, 1, 0, 0, 1, 1]))

636 10

637

638 # n = 10 and 5 true bits

639 >>> leadingones(np.array([0, 0, 1, 1, 0, 1, 1, 1, 0, 0]))

640 10

641

642 # n = 10 and 5 true bits

643 >>> leadingones(np.array([0, 1, 1, 1, 1, 0, 0, 1, 0, 0]))

644 10

645

646 # n = 10 and 6 true bits

647 >>> leadingones(np.array([1, 0, 1, 1, 1, 1, 1, 0, 0, 0]))

648 9

649

650 # n = 10 and 6 true bits

651 >>> leadingones(np.array([1, 1, 1, 0, 1, 0, 1, 1, 0, 0]))

652 7

653

654 # n = 10 and 6 true bits

655 >>> leadingones(np.array([1, 1, 1, 0, 1, 0, 1, 0, 0, 1]))

656 7

657

658 # n = 10 and 7 true bits

659 >>> leadingones(np.array([0, 1, 1, 1, 1, 1, 0, 1, 1, 0]))

660 10

661

662 # n = 10 and 7 true bits

663 >>> leadingones(np.array([0, 1, 0, 1, 1, 1, 1, 1, 1, 0]))

664 10

665

666 # n = 10 and 7 true bits

667 >>> leadingones(np.array([1, 1, 1, 1, 1, 0, 0, 1, 0, 1]))

668 5

669

670 # n = 10 and 8 true bits

671 >>> leadingones(np.array([1, 0, 1, 1, 1, 1, 1, 1, 0, 1]))

672 9

673

674 # n = 10 and 8 true bits

675 >>> leadingones(np.array([1, 1, 1, 0, 1, 1, 0, 1, 1, 1]))

676 7

677

678 # n = 10 and 8 true bits

679 >>> leadingones(np.array([1, 1, 1, 1, 0, 0, 1, 1, 1, 1]))

680 6

681

682 # n = 10 and 9 true bits

683 >>> leadingones(np.array([1, 1, 1, 1, 0, 1, 1, 1, 1, 1]))

684 6

685

686 # n = 10 and 9 true bits

687 >>> leadingones(np.array([1, 0, 1, 1, 1, 1, 1, 1, 1, 1]))

688 9

689

690 # n = 10 and 9 true bits

691 >>> leadingones(np.array([0, 1, 1, 1, 1, 1, 1, 1, 1, 1]))

692 10

693

694 # n = 10 and 10 true bits

695 >>> leadingones(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]))

696 0

697 """

698 xlen: Final[int] = len(x)

699 for i in range(xlen):

700 if not x[i]:

701 return xlen - i

702 return 0

703

704

705class LeadingOnes(BitStringProblem):

706 """Maximize the number of leading ones in a bit string."""

707

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

709 """

710 Initialize the leading ones objective function.

711

712 :param n: the dimension of the problem

713

714 >>> LeadingOnes(55).n

715 55

716 >>> LeadingOnes(4).evaluate(np.array([True, True, True, False]))

717 1

718 """

719 super().__init__(n)

720 self.evaluate = leadingones # type: ignore

721

722 def __str__(self) -> str:

723 """

724 Get the name of the leadingones objective function.

725

726 :return: `leadingones_` + lenth of string

727

728 >>> LeadingOnes(10)

729 leadingones_10

730 """

731 return f"leadingones_{self.n}"

732

733 @classmethod

734 def default_instances(

735 cls: type, scale_min: int = 2, scale_max: int = 4096) \

736 -> Iterator[Callable[[], "LeadingOnes"]]:

737 """

738 Get the 163 default instances of the :class:`LeadingOnes` problem.

739

740 :param scale_min: the minimum permitted scale, by default `2`

741 :param scale_max: the maximum permitted scale, by default `4096`

742 :returns: a sequence of default :class:`LeadingOnes` instances

743

744 >>> len(list(LeadingOnes.default_instances()))

745 163

746

747 >>> [x() for x in LeadingOnes.default_instances()]

748 [leadingones_2, leadingones_3, leadingones_4, leadingones_5, \

749leadingones_6, leadingones_7, leadingones_8, leadingones_9, leadingones_10, \

750leadingones_11, leadingones_12, leadingones_13, leadingones_14, \

751leadingones_15, leadingones_16, leadingones_17, leadingones_18, \

752leadingones_19, leadingones_20, leadingones_21, leadingones_22, \

753leadingones_23, leadingones_24, leadingones_25, leadingones_26, \

754leadingones_27, leadingones_28, leadingones_29, leadingones_30, \

755leadingones_31, leadingones_32, leadingones_33, leadingones_36, \

756leadingones_40, leadingones_41, leadingones_42, leadingones_44, \

757leadingones_48, leadingones_49, leadingones_50, leadingones_55, \

758leadingones_59, leadingones_60, leadingones_64, leadingones_66, \

759leadingones_70, leadingones_77, leadingones_79, leadingones_80, \

760leadingones_81, leadingones_85, leadingones_88, leadingones_90, \

761leadingones_96, leadingones_99, leadingones_100, leadingones_107, \

762leadingones_111, leadingones_121, leadingones_125, leadingones_128, \

763leadingones_144, leadingones_149, leadingones_169, leadingones_170, \

764leadingones_192, leadingones_196, leadingones_199, leadingones_200, \

765leadingones_222, leadingones_225, leadingones_243, leadingones_256, \

766leadingones_269, leadingones_289, leadingones_300, leadingones_324, \

767leadingones_333, leadingones_341, leadingones_343, leadingones_359, \

768leadingones_361, leadingones_384, leadingones_400, leadingones_441, \

769leadingones_444, leadingones_479, leadingones_484, leadingones_500, \

770leadingones_512, leadingones_529, leadingones_555, leadingones_576, \

771leadingones_600, leadingones_625, leadingones_641, leadingones_666, \

772leadingones_676, leadingones_682, leadingones_700, leadingones_729, \

773leadingones_768, leadingones_777, leadingones_784, leadingones_800, \

774leadingones_841, leadingones_857, leadingones_888, leadingones_900, \

775leadingones_961, leadingones_999, leadingones_1000, leadingones_1024, \

776leadingones_1089, leadingones_1111, leadingones_1151, leadingones_1156, \

777leadingones_1225, leadingones_1296, leadingones_1365, leadingones_1369, \

778leadingones_1444, leadingones_1521, leadingones_1536, leadingones_1543, \

779leadingones_1600, leadingones_1681, leadingones_1764, leadingones_1849, \

780leadingones_1936, leadingones_2000, leadingones_2025, leadingones_2048, \

781leadingones_2063, leadingones_2116, leadingones_2187, leadingones_2209, \

782leadingones_2222, leadingones_2304, leadingones_2401, leadingones_2500, \

783leadingones_2601, leadingones_2704, leadingones_2730, leadingones_2753, \

784leadingones_2809, leadingones_2916, leadingones_3000, leadingones_3025, \

785leadingones_3072, leadingones_3125, leadingones_3136, leadingones_3249, \

786leadingones_3333, leadingones_3364, leadingones_3481, leadingones_3600, \

787leadingones_3671, leadingones_3721, leadingones_3844, leadingones_3969, \

788leadingones_4000, leadingones_4096]

789 """

790 return cast("Iterator[Callable[[], LeadingOnes]]",

791 super().default_instances( # type: ignore

792 scale_min, scale_max))

Coverage for moptipy / examples / bitstrings / leadingones.py: 75%

20 statements