Coverage for /usr/lib/python3/dist-packages/sympy/combinatorics/partitions.py: 18%

1from sympy.core import Basic, Dict, sympify, Tuple

2from sympy.core.numbers import Integer

3from sympy.core.sorting import default_sort_key

4from sympy.core.sympify import _sympify

5from sympy.functions.combinatorial.numbers import bell

6from sympy.matrices import zeros

7from sympy.sets.sets import FiniteSet, Union

8from sympy.utilities.iterables import flatten, group

9from sympy.utilities.misc import as_int

12from collections import defaultdict

15class Partition(FiniteSet):

16 """

17 This class represents an abstract partition.

19 A partition is a set of disjoint sets whose union equals a given set.

21 See Also

22 ========

24 sympy.utilities.iterables.partitions,

25 sympy.utilities.iterables.multiset_partitions

26 """

28 _rank = None

29 _partition = None

31 def __new__(cls, *partition):

32 """

33 Generates a new partition object.

35 This method also verifies if the arguments passed are

36 valid and raises a ValueError if they are not.

38 Examples

39 ========

41 Creating Partition from Python lists:

43 >>> from sympy.combinatorics import Partition

44 >>> a = Partition([1, 2], [3])

45 >>> a

46 Partition({3}, {1, 2})

47 >>> a.partition

48 [[1, 2], [3]]

49 >>> len(a)

50 2

51 >>> a.members

52 (1, 2, 3)

54 Creating Partition from Python sets:

56 >>> Partition({1, 2, 3}, {4, 5})

57 Partition({4, 5}, {1, 2, 3})

59 Creating Partition from SymPy finite sets:

61 >>> from sympy import FiniteSet

62 >>> a = FiniteSet(1, 2, 3)

63 >>> b = FiniteSet(4, 5)

64 >>> Partition(a, b)

65 Partition({4, 5}, {1, 2, 3})

66 """

67 args = []

68 dups = False

69 for arg in partition:

70 if isinstance(arg, list):

71 as_set = set(arg)

72 if len(as_set) < len(arg):

73 dups = True

74 break # error below

75 arg = as_set

76 args.append(_sympify(arg))

78 if not all(isinstance(part, FiniteSet) for part in args):

79 raise ValueError(

80 "Each argument to Partition should be " \

81 "a list, set, or a FiniteSet")

83 # sort so we have a canonical reference for RGS

84 U = Union(*args)

85 if dups or len(U) < sum(len(arg) for arg in args):

86 raise ValueError("Partition contained duplicate elements.")

88 obj = FiniteSet.__new__(cls, *args)

89 obj.members = tuple(U)

90 obj.size = len(U)

91 return obj

93 def sort_key(self, order=None):

94 """Return a canonical key that can be used for sorting.

96 Ordering is based on the size and sorted elements of the partition

97 and ties are broken with the rank.

99 Examples

100 ========

101

102 >>> from sympy import default_sort_key

103 >>> from sympy.combinatorics import Partition

104 >>> from sympy.abc import x

105 >>> a = Partition([1, 2])

106 >>> b = Partition([3, 4])

107 >>> c = Partition([1, x])

108 >>> d = Partition(list(range(4)))

109 >>> l = [d, b, a + 1, a, c]

110 >>> l.sort(key=default_sort_key); l

111 [Partition({1, 2}), Partition({1}, {2}), Partition({1, x}), Partition({3, 4}), Partition({0, 1, 2, 3})]

112 """

113 if order is None:

114 members = self.members

115 else:

116 members = tuple(sorted(self.members,

117 key=lambda w: default_sort_key(w, order)))

118 return tuple(map(default_sort_key, (self.size, members, self.rank)))

119

120 @property

121 def partition(self):

122 """Return partition as a sorted list of lists.

123

124 Examples

125 ========

126

127 >>> from sympy.combinatorics import Partition

128 >>> Partition([1], [2, 3]).partition

129 [[1], [2, 3]]

130 """

131 if self._partition is None:

132 self._partition = sorted([sorted(p, key=default_sort_key)

133 for p in self.args])

134 return self._partition

135

136 def __add__(self, other):

137 """

138 Return permutation whose rank is ``other`` greater than current rank,

139 (mod the maximum rank for the set).

140

141 Examples

142 ========

143

144 >>> from sympy.combinatorics import Partition

145 >>> a = Partition([1, 2], [3])

146 >>> a.rank

147 1

148 >>> (a + 1).rank

149 2

150 >>> (a + 100).rank

151 1

152 """

153 other = as_int(other)

154 offset = self.rank + other

155 result = RGS_unrank((offset) %

156 RGS_enum(self.size),

157 self.size)

158 return Partition.from_rgs(result, self.members)

159

160 def __sub__(self, other):

161 """

162 Return permutation whose rank is ``other`` less than current rank,

163 (mod the maximum rank for the set).

164

165 Examples

166 ========

167

168 >>> from sympy.combinatorics import Partition

169 >>> a = Partition([1, 2], [3])

170 >>> a.rank

171 1

172 >>> (a - 1).rank

173 0

174 >>> (a - 100).rank

175 1

176 """

177 return self.__add__(-other)

178

179 def __le__(self, other):

180 """

181 Checks if a partition is less than or equal to

182 the other based on rank.

183

184 Examples

185 ========

186

187 >>> from sympy.combinatorics import Partition

188 >>> a = Partition([1, 2], [3, 4, 5])

189 >>> b = Partition([1], [2, 3], [4], [5])

190 >>> a.rank, b.rank

191 (9, 34)

192 >>> a <= a

193 True

194 >>> a <= b

195 True

196 """

197 return self.sort_key() <= sympify(other).sort_key()

198

199 def __lt__(self, other):

200 """

201 Checks if a partition is less than the other.

202

203 Examples

204 ========

205

206 >>> from sympy.combinatorics import Partition

207 >>> a = Partition([1, 2], [3, 4, 5])

208 >>> b = Partition([1], [2, 3], [4], [5])

209 >>> a.rank, b.rank

210 (9, 34)

211 >>> a < b

212 True

213 """

214 return self.sort_key() < sympify(other).sort_key()

215

216 @property

217 def rank(self):

218 """

219 Gets the rank of a partition.

220

221 Examples

222 ========

223

224 >>> from sympy.combinatorics import Partition

225 >>> a = Partition([1, 2], [3], [4, 5])

226 >>> a.rank

227 13

228 """

229 if self._rank is not None:

230 return self._rank

231 self._rank = RGS_rank(self.RGS)

232 return self._rank

233

234 @property

235 def RGS(self):

236 """

237 Returns the "restricted growth string" of the partition.

238

239 Explanation

240 ===========

241

242 The RGS is returned as a list of indices, L, where L[i] indicates

243 the block in which element i appears. For example, in a partition

244 of 3 elements (a, b, c) into 2 blocks ([c], [a, b]) the RGS is

245 [1, 1, 0]: "a" is in block 1, "b" is in block 1 and "c" is in block 0.

246

247 Examples

248 ========

249

250 >>> from sympy.combinatorics import Partition

251 >>> a = Partition([1, 2], [3], [4, 5])

252 >>> a.members

253 (1, 2, 3, 4, 5)

254 >>> a.RGS

255 (0, 0, 1, 2, 2)

256 >>> a + 1

257 Partition({3}, {4}, {5}, {1, 2})

258 >>> _.RGS

259 (0, 0, 1, 2, 3)

260 """

261 rgs = {}

262 partition = self.partition

263 for i, part in enumerate(partition):

264 for j in part:

265 rgs[j] = i

266 return tuple([rgs[i] for i in sorted(

267 [i for p in partition for i in p], key=default_sort_key)])

268

269 @classmethod

270 def from_rgs(self, rgs, elements):

271 """

272 Creates a set partition from a restricted growth string.

273

274 Explanation

275 ===========

276

277 The indices given in rgs are assumed to be the index

278 of the element as given in elements *as provided* (the

279 elements are not sorted by this routine). Block numbering

280 starts from 0. If any block was not referenced in ``rgs``

281 an error will be raised.

282

283 Examples

284 ========

285

286 >>> from sympy.combinatorics import Partition

287 >>> Partition.from_rgs([0, 1, 2, 0, 1], list('abcde'))

288 Partition({c}, {a, d}, {b, e})

289 >>> Partition.from_rgs([0, 1, 2, 0, 1], list('cbead'))

290 Partition({e}, {a, c}, {b, d})

291 >>> a = Partition([1, 4], [2], [3, 5])

292 >>> Partition.from_rgs(a.RGS, a.members)

293 Partition({2}, {1, 4}, {3, 5})

294 """

295 if len(rgs) != len(elements):

296 raise ValueError('mismatch in rgs and element lengths')

297 max_elem = max(rgs) + 1

298 partition = [[] for i in range(max_elem)]

299 j = 0

300 for i in rgs:

301 partition[i].append(elements[j])

302 j += 1

303 if not all(p for p in partition):

304 raise ValueError('some blocks of the partition were empty.')

305 return Partition(*partition)

306

307

308class IntegerPartition(Basic):

309 """

310 This class represents an integer partition.

311

312 Explanation

313 ===========

314

315 In number theory and combinatorics, a partition of a positive integer,

316 ``n``, also called an integer partition, is a way of writing ``n`` as a

317 list of positive integers that sum to n. Two partitions that differ only

318 in the order of summands are considered to be the same partition; if order

319 matters then the partitions are referred to as compositions. For example,

320 4 has five partitions: [4], [3, 1], [2, 2], [2, 1, 1], and [1, 1, 1, 1];

321 the compositions [1, 2, 1] and [1, 1, 2] are the same as partition

322 [2, 1, 1].

323

324 See Also

325 ========

326

327 sympy.utilities.iterables.partitions,

328 sympy.utilities.iterables.multiset_partitions

329

330 References

331 ==========

332

333 .. [1] https://en.wikipedia.org/wiki/Partition_%28number_theory%29

334 """

335

336 _dict = None

337 _keys = None

338

339 def __new__(cls, partition, integer=None):

340 """

341 Generates a new IntegerPartition object from a list or dictionary.

342

343 Explanation

344 ===========

345

346 The partition can be given as a list of positive integers or a

347 dictionary of (integer, multiplicity) items. If the partition is

348 preceded by an integer an error will be raised if the partition

349 does not sum to that given integer.

350

351 Examples

352 ========

353

354 >>> from sympy.combinatorics.partitions import IntegerPartition

355 >>> a = IntegerPartition([5, 4, 3, 1, 1])

356 >>> a

357 IntegerPartition(14, (5, 4, 3, 1, 1))

358 >>> print(a)

359 [5, 4, 3, 1, 1]

360 >>> IntegerPartition({1:3, 2:1})

361 IntegerPartition(5, (2, 1, 1, 1))

362

363 If the value that the partition should sum to is given first, a check

364 will be made to see n error will be raised if there is a discrepancy:

365

366 >>> IntegerPartition(10, [5, 4, 3, 1])

367 Traceback (most recent call last):

368 ...

369 ValueError: The partition is not valid

370

371 """

372 if integer is not None:

373 integer, partition = partition, integer

374 if isinstance(partition, (dict, Dict)):

375 _ = []

376 for k, v in sorted(partition.items(), reverse=True):

377 if not v:

378 continue

379 k, v = as_int(k), as_int(v)

380 _.extend([k]*v)

381 partition = tuple(_)

382 else:

383 partition = tuple(sorted(map(as_int, partition), reverse=True))

384 sum_ok = False

385 if integer is None:

386 integer = sum(partition)

387 sum_ok = True

388 else:

389 integer = as_int(integer)

390

391 if not sum_ok and sum(partition) != integer:

392 raise ValueError("Partition did not add to %s" % integer)

393 if any(i < 1 for i in partition):

394 raise ValueError("All integer summands must be greater than one")

395

396 obj = Basic.__new__(cls, Integer(integer), Tuple(*partition))

397 obj.partition = list(partition)

398 obj.integer = integer

399 return obj

400

401 def prev_lex(self):

402 """Return the previous partition of the integer, n, in lexical order,

403 wrapping around to [1, ..., 1] if the partition is [n].

404

405 Examples

406 ========

407

408 >>> from sympy.combinatorics.partitions import IntegerPartition

409 >>> p = IntegerPartition([4])

410 >>> print(p.prev_lex())

411 [3, 1]

412 >>> p.partition > p.prev_lex().partition

413 True

414 """

415 d = defaultdict(int)

416 d.update(self.as_dict())

417 keys = self._keys

418 if keys == [1]:

419 return IntegerPartition({self.integer: 1})

420 if keys[-1] != 1:

421 d[keys[-1]] -= 1

422 if keys[-1] == 2:

423 d[1] = 2

424 else:

425 d[keys[-1] - 1] = d[1] = 1

426 else:

427 d[keys[-2]] -= 1

428 left = d[1] + keys[-2]

429 new = keys[-2]

430 d[1] = 0

431 while left:

432 new -= 1

433 if left - new >= 0:

434 d[new] += left//new

435 left -= d[new]*new

436 return IntegerPartition(self.integer, d)

437

438 def next_lex(self):

439 """Return the next partition of the integer, n, in lexical order,

440 wrapping around to [n] if the partition is [1, ..., 1].

441

442 Examples

443 ========

444

445 >>> from sympy.combinatorics.partitions import IntegerPartition

446 >>> p = IntegerPartition([3, 1])

447 >>> print(p.next_lex())

448 [4]

449 >>> p.partition < p.next_lex().partition

450 True

451 """

452 d = defaultdict(int)

453 d.update(self.as_dict())

454 key = self._keys

455 a = key[-1]

456 if a == self.integer:

457 d.clear()

458 d[1] = self.integer

459 elif a == 1:

460 if d[a] > 1:

461 d[a + 1] += 1

462 d[a] -= 2

463 else:

464 b = key[-2]

465 d[b + 1] += 1

466 d[1] = (d[b] - 1)*b

467 d[b] = 0

468 else:

469 if d[a] > 1:

470 if len(key) == 1:

471 d.clear()

472 d[a + 1] = 1

473 d[1] = self.integer - a - 1

474 else:

475 a1 = a + 1

476 d[a1] += 1

477 d[1] = d[a]*a - a1

478 d[a] = 0

479 else:

480 b = key[-2]

481 b1 = b + 1

482 d[b1] += 1

483 need = d[b]*b + d[a]*a - b1

484 d[a] = d[b] = 0

485 d[1] = need

486 return IntegerPartition(self.integer, d)

487

488 def as_dict(self):

489 """Return the partition as a dictionary whose keys are the

490 partition integers and the values are the multiplicity of that

491 integer.

492

493 Examples

494 ========

495

496 >>> from sympy.combinatorics.partitions import IntegerPartition

497 >>> IntegerPartition([1]*3 + [2] + [3]*4).as_dict()

498 {1: 3, 2: 1, 3: 4}

499 """

500 if self._dict is None:

501 groups = group(self.partition, multiple=False)

502 self._keys = [g[0] for g in groups]

503 self._dict = dict(groups)

504 return self._dict

505

506 @property

507 def conjugate(self):

508 """

509 Computes the conjugate partition of itself.

510

511 Examples

512 ========

513

514 >>> from sympy.combinatorics.partitions import IntegerPartition

515 >>> a = IntegerPartition([6, 3, 3, 2, 1])

516 >>> a.conjugate

517 [5, 4, 3, 1, 1, 1]

518 """

519 j = 1

520 temp_arr = list(self.partition) + [0]

521 k = temp_arr[0]

522 b = [0]*k

523 while k > 0:

524 while k > temp_arr[j]:

525 b[k - 1] = j

526 k -= 1

527 j += 1

528 return b

529

530 def __lt__(self, other):

531 """Return True if self is less than other when the partition

532 is listed from smallest to biggest.

533

534 Examples

535 ========

536

537 >>> from sympy.combinatorics.partitions import IntegerPartition

538 >>> a = IntegerPartition([3, 1])

539 >>> a < a

540 False

541 >>> b = a.next_lex()

542 >>> a < b

543 True

544 >>> a == b

545 False

546 """

547 return list(reversed(self.partition)) < list(reversed(other.partition))

548

549 def __le__(self, other):

550 """Return True if self is less than other when the partition

551 is listed from smallest to biggest.

552

553 Examples

554 ========

555

556 >>> from sympy.combinatorics.partitions import IntegerPartition

557 >>> a = IntegerPartition([4])

558 >>> a <= a

559 True

560 """

561 return list(reversed(self.partition)) <= list(reversed(other.partition))

562

563 def as_ferrers(self, char='#'):

564 """

565 Prints the ferrer diagram of a partition.

566

567 Examples

568 ========

569

570 >>> from sympy.combinatorics.partitions import IntegerPartition

571 >>> print(IntegerPartition([1, 1, 5]).as_ferrers())

572 #####

573 #

574 #

575 """

576 return "\n".join([char*i for i in self.partition])

577

578 def __str__(self):

579 return str(list(self.partition))

580

581

582def random_integer_partition(n, seed=None):

583 """

584 Generates a random integer partition summing to ``n`` as a list

585 of reverse-sorted integers.

586

587 Examples

588 ========

589

590 >>> from sympy.combinatorics.partitions import random_integer_partition

591

592 For the following, a seed is given so a known value can be shown; in

593 practice, the seed would not be given.

594

595 >>> random_integer_partition(100, seed=[1, 1, 12, 1, 2, 1, 85, 1])

596 [85, 12, 2, 1]

597 >>> random_integer_partition(10, seed=[1, 2, 3, 1, 5, 1])

598 [5, 3, 1, 1]

599 >>> random_integer_partition(1)

600 [1]

601 """

602 from sympy.core.random import _randint

603

604 n = as_int(n)

605 if n < 1:

606 raise ValueError('n must be a positive integer')

607

608 randint = _randint(seed)

609

610 partition = []

611 while (n > 0):

612 k = randint(1, n)

613 mult = randint(1, n//k)

614 partition.append((k, mult))

615 n -= k*mult

616 partition.sort(reverse=True)

617 partition = flatten([[k]*m for k, m in partition])

618 return partition

619

620

621def RGS_generalized(m):

622 """

623 Computes the m + 1 generalized unrestricted growth strings

624 and returns them as rows in matrix.

625

626 Examples

627 ========

628

629 >>> from sympy.combinatorics.partitions import RGS_generalized

630 >>> RGS_generalized(6)

631 Matrix([

632 [ 1, 1, 1, 1, 1, 1, 1],

633 [ 1, 2, 3, 4, 5, 6, 0],

634 [ 2, 5, 10, 17, 26, 0, 0],

635 [ 5, 15, 37, 77, 0, 0, 0],

636 [ 15, 52, 151, 0, 0, 0, 0],

637 [ 52, 203, 0, 0, 0, 0, 0],

638 [203, 0, 0, 0, 0, 0, 0]])

639 """

640 d = zeros(m + 1)

641 for i in range(m + 1):

642 d[0, i] = 1

643

644 for i in range(1, m + 1):

645 for j in range(m):

646 if j <= m - i:

647 d[i, j] = j * d[i - 1, j] + d[i - 1, j + 1]

648 else:

649 d[i, j] = 0

650 return d

651

652

653def RGS_enum(m):

654 """

655 RGS_enum computes the total number of restricted growth strings

656 possible for a superset of size m.

657

658 Examples

659 ========

660

661 >>> from sympy.combinatorics.partitions import RGS_enum

662 >>> from sympy.combinatorics import Partition

663 >>> RGS_enum(4)

664 15

665 >>> RGS_enum(5)

666 52

667 >>> RGS_enum(6)

668 203

669

670 We can check that the enumeration is correct by actually generating

671 the partitions. Here, the 15 partitions of 4 items are generated:

672

673 >>> a = Partition(list(range(4)))

674 >>> s = set()

675 >>> for i in range(20):

676 ... s.add(a)

677 ... a += 1

678 ...

679 >>> assert len(s) == 15

680

681 """

682 if (m < 1):

683 return 0

684 elif (m == 1):

685 return 1

686 else:

687 return bell(m)

688

689

690def RGS_unrank(rank, m):

691 """

692 Gives the unranked restricted growth string for a given

693 superset size.

694

695 Examples

696 ========

697

698 >>> from sympy.combinatorics.partitions import RGS_unrank

699 >>> RGS_unrank(14, 4)

700 [0, 1, 2, 3]

701 >>> RGS_unrank(0, 4)

702 [0, 0, 0, 0]

703 """

704 if m < 1:

705 raise ValueError("The superset size must be >= 1")

706 if rank < 0 or RGS_enum(m) <= rank:

707 raise ValueError("Invalid arguments")

708

709 L = [1] * (m + 1)

710 j = 1

711 D = RGS_generalized(m)

712 for i in range(2, m + 1):

713 v = D[m - i, j]

714 cr = j*v

715 if cr <= rank:

716 L[i] = j + 1

717 rank -= cr

718 j += 1

719 else:

720 L[i] = int(rank / v + 1)

721 rank %= v

722 return [x - 1 for x in L[1:]]

723

724

725def RGS_rank(rgs):

726 """

727 Computes the rank of a restricted growth string.

728

729 Examples

730 ========

731

732 >>> from sympy.combinatorics.partitions import RGS_rank, RGS_unrank

733 >>> RGS_rank([0, 1, 2, 1, 3])

734 42

735 >>> RGS_rank(RGS_unrank(4, 7))

736 4

737 """

738 rgs_size = len(rgs)

739 rank = 0

740 D = RGS_generalized(rgs_size)

741 for i in range(1, rgs_size):

742 n = len(rgs[(i + 1):])

743 m = max(rgs[0:i])

744 rank += D[n, m + 1] * rgs[i]

745 return rank