Coverage for /usr/lib/python3/dist-packages/sympy/combinatorics/subsets.py: 29%

1from itertools import combinations 

2 

3from sympy.combinatorics.graycode import GrayCode 

4 

5 

6class Subset(): 

7 """ 

8 Represents a basic subset object. 

9 

10 Explanation 

11 =========== 

12 

13 We generate subsets using essentially two techniques, 

14 binary enumeration and lexicographic enumeration. 

15 The Subset class takes two arguments, the first one 

16 describes the initial subset to consider and the second 

17 describes the superset. 

18 

19 Examples 

20 ======== 

21 

22 >>> from sympy.combinatorics import Subset 

23 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

24 >>> a.next_binary().subset 

25 ['b'] 

26 >>> a.prev_binary().subset 

27 ['c'] 

28 """ 

29 

30 _rank_binary = None 

31 _rank_lex = None 

32 _rank_graycode = None 

33 _subset = None 

34 _superset = None 

35 

36 def __new__(cls, subset, superset): 

37 """ 

38 Default constructor. 

39 

40 It takes the ``subset`` and its ``superset`` as its parameters. 

41 

42 Examples 

43 ======== 

44 

45 >>> from sympy.combinatorics import Subset 

46 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

47 >>> a.subset 

48 ['c', 'd'] 

49 >>> a.superset 

50 ['a', 'b', 'c', 'd'] 

51 >>> a.size 

52 2 

53 """ 

54 if len(subset) > len(superset): 

55 raise ValueError('Invalid arguments have been provided. The ' 

56 'superset must be larger than the subset.') 

57 for elem in subset: 

58 if elem not in superset: 

59 raise ValueError('The superset provided is invalid as it does ' 

60 'not contain the element {}'.format(elem)) 

61 obj = object.__new__(cls) 

62 obj._subset = subset 

63 obj._superset = superset 

64 return obj 

65 

66 def __eq__(self, other): 

67 """Return a boolean indicating whether a == b on the basis of 

68 whether both objects are of the class Subset and if the values 

69 of the subset and superset attributes are the same. 

70 """ 

71 if not isinstance(other, Subset): 

72 return NotImplemented 

73 return self.subset == other.subset and self.superset == other.superset 

74 

75 def iterate_binary(self, k): 

76 """ 

77 This is a helper function. It iterates over the 

78 binary subsets by ``k`` steps. This variable can be 

79 both positive or negative. 

80 

81 Examples 

82 ======== 

83 

84 >>> from sympy.combinatorics import Subset 

85 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

86 >>> a.iterate_binary(-2).subset 

87 ['d'] 

88 >>> a = Subset(['a', 'b', 'c'], ['a', 'b', 'c', 'd']) 

89 >>> a.iterate_binary(2).subset 

90 [] 

91 

92 See Also 

93 ======== 

94 

95 next_binary, prev_binary 

96 """ 

97 bin_list = Subset.bitlist_from_subset(self.subset, self.superset) 

98 n = (int(''.join(bin_list), 2) + k) % 2**self.superset_size 

99 bits = bin(n)[2:].rjust(self.superset_size, '0') 

100 return Subset.subset_from_bitlist(self.superset, bits) 

101 

102 def next_binary(self): 

103 """ 

104 Generates the next binary ordered subset. 

105 

106 Examples 

107 ======== 

108 

109 >>> from sympy.combinatorics import Subset 

110 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

111 >>> a.next_binary().subset 

112 ['b'] 

113 >>> a = Subset(['a', 'b', 'c', 'd'], ['a', 'b', 'c', 'd']) 

114 >>> a.next_binary().subset 

115 [] 

116 

117 See Also 

118 ======== 

119 

120 prev_binary, iterate_binary 

121 """ 

122 return self.iterate_binary(1) 

123 

124 def prev_binary(self): 

125 """ 

126 Generates the previous binary ordered subset. 

127 

128 Examples 

129 ======== 

130 

131 >>> from sympy.combinatorics import Subset 

132 >>> a = Subset([], ['a', 'b', 'c', 'd']) 

133 >>> a.prev_binary().subset 

134 ['a', 'b', 'c', 'd'] 

135 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

136 >>> a.prev_binary().subset 

137 ['c'] 

138 

139 See Also 

140 ======== 

141 

142 next_binary, iterate_binary 

143 """ 

144 return self.iterate_binary(-1) 

145 

146 def next_lexicographic(self): 

147 """ 

148 Generates the next lexicographically ordered subset. 

149 

150 Examples 

151 ======== 

152 

153 >>> from sympy.combinatorics import Subset 

154 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

155 >>> a.next_lexicographic().subset 

156 ['d'] 

157 >>> a = Subset(['d'], ['a', 'b', 'c', 'd']) 

158 >>> a.next_lexicographic().subset 

159 [] 

160 

161 See Also 

162 ======== 

163 

164 prev_lexicographic 

165 """ 

166 i = self.superset_size - 1 

167 indices = Subset.subset_indices(self.subset, self.superset) 

168 

169 if i in indices: 

170 if i - 1 in indices: 

171 indices.remove(i - 1) 

172 else: 

173 indices.remove(i) 

174 i = i - 1 

175 while i >= 0 and i not in indices: 

176 i = i - 1 

177 if i >= 0: 

178 indices.remove(i) 

179 indices.append(i+1) 

180 else: 

181 while i not in indices and i >= 0: 

182 i = i - 1 

183 indices.append(i + 1) 

184 

185 ret_set = [] 

186 super_set = self.superset 

187 for i in indices: 

188 ret_set.append(super_set[i]) 

189 return Subset(ret_set, super_set) 

190 

191 def prev_lexicographic(self): 

192 """ 

193 Generates the previous lexicographically ordered subset. 

194 

195 Examples 

196 ======== 

197 

198 >>> from sympy.combinatorics import Subset 

199 >>> a = Subset([], ['a', 'b', 'c', 'd']) 

200 >>> a.prev_lexicographic().subset 

201 ['d'] 

202 >>> a = Subset(['c','d'], ['a', 'b', 'c', 'd']) 

203 >>> a.prev_lexicographic().subset 

204 ['c'] 

205 

206 See Also 

207 ======== 

208 

209 next_lexicographic 

210 """ 

211 i = self.superset_size - 1 

212 indices = Subset.subset_indices(self.subset, self.superset) 

213 

214 while i >= 0 and i not in indices: 

215 i = i - 1 

216 

217 if i == 0 or i - 1 in indices: 

218 indices.remove(i) 

219 else: 

220 if i >= 0: 

221 indices.remove(i) 

222 indices.append(i - 1) 

223 indices.append(self.superset_size - 1) 

224 

225 ret_set = [] 

226 super_set = self.superset 

227 for i in indices: 

228 ret_set.append(super_set[i]) 

229 return Subset(ret_set, super_set) 

230 

231 def iterate_graycode(self, k): 

232 """ 

233 Helper function used for prev_gray and next_gray. 

234 It performs ``k`` step overs to get the respective Gray codes. 

235 

236 Examples 

237 ======== 

238 

239 >>> from sympy.combinatorics import Subset 

240 >>> a = Subset([1, 2, 3], [1, 2, 3, 4]) 

241 >>> a.iterate_graycode(3).subset 

242 [1, 4] 

243 >>> a.iterate_graycode(-2).subset 

244 [1, 2, 4] 

245 

246 See Also 

247 ======== 

248 

249 next_gray, prev_gray 

250 """ 

251 unranked_code = GrayCode.unrank(self.superset_size, 

252 (self.rank_gray + k) % self.cardinality) 

253 return Subset.subset_from_bitlist(self.superset, 

254 unranked_code) 

255 

256 def next_gray(self): 

257 """ 

258 Generates the next Gray code ordered subset. 

259 

260 Examples 

261 ======== 

262 

263 >>> from sympy.combinatorics import Subset 

264 >>> a = Subset([1, 2, 3], [1, 2, 3, 4]) 

265 >>> a.next_gray().subset 

266 [1, 3] 

267 

268 See Also 

269 ======== 

270 

271 iterate_graycode, prev_gray 

272 """ 

273 return self.iterate_graycode(1) 

274 

275 def prev_gray(self): 

276 """ 

277 Generates the previous Gray code ordered subset. 

278 

279 Examples 

280 ======== 

281 

282 >>> from sympy.combinatorics import Subset 

283 >>> a = Subset([2, 3, 4], [1, 2, 3, 4, 5]) 

284 >>> a.prev_gray().subset 

285 [2, 3, 4, 5] 

286 

287 See Also 

288 ======== 

289 

290 iterate_graycode, next_gray 

291 """ 

292 return self.iterate_graycode(-1) 

293 

294 @property 

295 def rank_binary(self): 

296 """ 

297 Computes the binary ordered rank. 

298 

299 Examples 

300 ======== 

301 

302 >>> from sympy.combinatorics import Subset 

303 >>> a = Subset([], ['a','b','c','d']) 

304 >>> a.rank_binary 

305 0 

306 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

307 >>> a.rank_binary 

308 3 

309 

310 See Also 

311 ======== 

312 

313 iterate_binary, unrank_binary 

314 """ 

315 if self._rank_binary is None: 

316 self._rank_binary = int("".join( 

317 Subset.bitlist_from_subset(self.subset, 

318 self.superset)), 2) 

319 return self._rank_binary 

320 

321 @property 

322 def rank_lexicographic(self): 

323 """ 

324 Computes the lexicographic ranking of the subset. 

325 

326 Examples 

327 ======== 

328 

329 >>> from sympy.combinatorics import Subset 

330 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

331 >>> a.rank_lexicographic 

332 14 

333 >>> a = Subset([2, 4, 5], [1, 2, 3, 4, 5, 6]) 

334 >>> a.rank_lexicographic 

335 43 

336 """ 

337 if self._rank_lex is None: 

338 def _ranklex(self, subset_index, i, n): 

339 if subset_index == [] or i > n: 

340 return 0 

341 if i in subset_index: 

342 subset_index.remove(i) 

343 return 1 + _ranklex(self, subset_index, i + 1, n) 

344 return 2**(n - i - 1) + _ranklex(self, subset_index, i + 1, n) 

345 indices = Subset.subset_indices(self.subset, self.superset) 

346 self._rank_lex = _ranklex(self, indices, 0, self.superset_size) 

347 return self._rank_lex 

348 

349 @property 

350 def rank_gray(self): 

351 """ 

352 Computes the Gray code ranking of the subset. 

353 

354 Examples 

355 ======== 

356 

357 >>> from sympy.combinatorics import Subset 

358 >>> a = Subset(['c','d'], ['a','b','c','d']) 

359 >>> a.rank_gray 

360 2 

361 >>> a = Subset([2, 4, 5], [1, 2, 3, 4, 5, 6]) 

362 >>> a.rank_gray 

363 27 

364 

365 See Also 

366 ======== 

367 

368 iterate_graycode, unrank_gray 

369 """ 

370 if self._rank_graycode is None: 

371 bits = Subset.bitlist_from_subset(self.subset, self.superset) 

372 self._rank_graycode = GrayCode(len(bits), start=bits).rank 

373 return self._rank_graycode 

374 

375 @property 

376 def subset(self): 

377 """ 

378 Gets the subset represented by the current instance. 

379 

380 Examples 

381 ======== 

382 

383 >>> from sympy.combinatorics import Subset 

384 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

385 >>> a.subset 

386 ['c', 'd'] 

387 

388 See Also 

389 ======== 

390 

391 superset, size, superset_size, cardinality 

392 """ 

393 return self._subset 

394 

395 @property 

396 def size(self): 

397 """ 

398 Gets the size of the subset. 

399 

400 Examples 

401 ======== 

402 

403 >>> from sympy.combinatorics import Subset 

404 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

405 >>> a.size 

406 2 

407 

408 See Also 

409 ======== 

410 

411 subset, superset, superset_size, cardinality 

412 """ 

413 return len(self.subset) 

414 

415 @property 

416 def superset(self): 

417 """ 

418 Gets the superset of the subset. 

419 

420 Examples 

421 ======== 

422 

423 >>> from sympy.combinatorics import Subset 

424 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

425 >>> a.superset 

426 ['a', 'b', 'c', 'd'] 

427 

428 See Also 

429 ======== 

430 

431 subset, size, superset_size, cardinality 

432 """ 

433 return self._superset 

434 

435 @property 

436 def superset_size(self): 

437 """ 

438 Returns the size of the superset. 

439 

440 Examples 

441 ======== 

442 

443 >>> from sympy.combinatorics import Subset 

444 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

445 >>> a.superset_size 

446 4 

447 

448 See Also 

449 ======== 

450 

451 subset, superset, size, cardinality 

452 """ 

453 return len(self.superset) 

454 

455 @property 

456 def cardinality(self): 

457 """ 

458 Returns the number of all possible subsets. 

459 

460 Examples 

461 ======== 

462 

463 >>> from sympy.combinatorics import Subset 

464 >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

465 >>> a.cardinality 

466 16 

467 

468 See Also 

469 ======== 

470 

471 subset, superset, size, superset_size 

472 """ 

473 return 2**(self.superset_size) 

474 

475 @classmethod 

476 def subset_from_bitlist(self, super_set, bitlist): 

477 """ 

478 Gets the subset defined by the bitlist. 

479 

480 Examples 

481 ======== 

482 

483 >>> from sympy.combinatorics import Subset 

484 >>> Subset.subset_from_bitlist(['a', 'b', 'c', 'd'], '0011').subset 

485 ['c', 'd'] 

486 

487 See Also 

488 ======== 

489 

490 bitlist_from_subset 

491 """ 

492 if len(super_set) != len(bitlist): 

493 raise ValueError("The sizes of the lists are not equal") 

494 ret_set = [] 

495 for i in range(len(bitlist)): 

496 if bitlist[i] == '1': 

497 ret_set.append(super_set[i]) 

498 return Subset(ret_set, super_set) 

499 

500 @classmethod 

501 def bitlist_from_subset(self, subset, superset): 

502 """ 

503 Gets the bitlist corresponding to a subset. 

504 

505 Examples 

506 ======== 

507 

508 >>> from sympy.combinatorics import Subset 

509 >>> Subset.bitlist_from_subset(['c', 'd'], ['a', 'b', 'c', 'd']) 

510 '0011' 

511 

512 See Also 

513 ======== 

514 

515 subset_from_bitlist 

516 """ 

517 bitlist = ['0'] * len(superset) 

518 if isinstance(subset, Subset): 

519 subset = subset.subset 

520 for i in Subset.subset_indices(subset, superset): 

521 bitlist[i] = '1' 

522 return ''.join(bitlist) 

523 

524 @classmethod 

525 def unrank_binary(self, rank, superset): 

526 """ 

527 Gets the binary ordered subset of the specified rank. 

528 

529 Examples 

530 ======== 

531 

532 >>> from sympy.combinatorics import Subset 

533 >>> Subset.unrank_binary(4, ['a', 'b', 'c', 'd']).subset 

534 ['b'] 

535 

536 See Also 

537 ======== 

538 

539 iterate_binary, rank_binary 

540 """ 

541 bits = bin(rank)[2:].rjust(len(superset), '0') 

542 return Subset.subset_from_bitlist(superset, bits) 

543 

544 @classmethod 

545 def unrank_gray(self, rank, superset): 

546 """ 

547 Gets the Gray code ordered subset of the specified rank. 

548 

549 Examples 

550 ======== 

551 

552 >>> from sympy.combinatorics import Subset 

553 >>> Subset.unrank_gray(4, ['a', 'b', 'c']).subset 

554 ['a', 'b'] 

555 >>> Subset.unrank_gray(0, ['a', 'b', 'c']).subset 

556 [] 

557 

558 See Also 

559 ======== 

560 

561 iterate_graycode, rank_gray 

562 """ 

563 graycode_bitlist = GrayCode.unrank(len(superset), rank) 

564 return Subset.subset_from_bitlist(superset, graycode_bitlist) 

565 

566 @classmethod 

567 def subset_indices(self, subset, superset): 

568 """Return indices of subset in superset in a list; the list is empty 

569 if all elements of ``subset`` are not in ``superset``. 

570 

571 Examples 

572 ======== 

573 

574 >>> from sympy.combinatorics import Subset 

575 >>> superset = [1, 3, 2, 5, 4] 

576 >>> Subset.subset_indices([3, 2, 1], superset) 

577 [1, 2, 0] 

578 >>> Subset.subset_indices([1, 6], superset) 

579 [] 

580 >>> Subset.subset_indices([], superset) 

581 [] 

582 

583 """ 

584 a, b = superset, subset 

585 sb = set(b) 

586 d = {} 

587 for i, ai in enumerate(a): 

588 if ai in sb: 

589 d[ai] = i 

590 sb.remove(ai) 

591 if not sb: 

592 break 

593 else: 

594 return [] 

595 return [d[bi] for bi in b] 

596 

597 

598def ksubsets(superset, k): 

599 """ 

600 Finds the subsets of size ``k`` in lexicographic order. 

601 

602 This uses the itertools generator. 

603 

604 Examples 

605 ======== 

606 

607 >>> from sympy.combinatorics.subsets import ksubsets 

608 >>> list(ksubsets([1, 2, 3], 2)) 

609 [(1, 2), (1, 3), (2, 3)] 

610 >>> list(ksubsets([1, 2, 3, 4, 5], 2)) 

611 [(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), \ 

612 (2, 5), (3, 4), (3, 5), (4, 5)] 

613 

614 See Also 

615 ======== 

616 

617 Subset 

618 """ 

619 return combinations(superset, k)