Partitions
Partitions¶
- class sympy.combinatorics.partitions.Partition(*partition)[source]¶
This class represents an abstract partition.
A partition is a set of disjoint sets whose union equals a given set.
- property RGS¶
Returns the “restricted growth string” of the partition.
Explanation
The RGS is returned as a list of indices, L, where L[i] indicates the block in which element i appears. For example, in a partition of 3 elements (a, b, c) into 2 blocks ([c], [a, b]) the RGS is [1, 1, 0]: “a” is in block 1, “b” is in block 1 and “c” is in block 0.
Examples
>>> from sympy.combinatorics import Partition >>> a = Partition([1, 2], [3], [4, 5]) >>> a.members (1, 2, 3, 4, 5) >>> a.RGS (0, 0, 1, 2, 2) >>> a + 1 Partition({3}, {4}, {5}, {1, 2}) >>> _.RGS (0, 0, 1, 2, 3)
- classmethod from_rgs(rgs, elements)[source]¶
Creates a set partition from a restricted growth string.
Explanation
The indices given in rgs are assumed to be the index of the element as given in elements as provided (the elements are not sorted by this routine). Block numbering starts from 0. If any block was not referenced in
rgsan error will be raised.Examples
>>> from sympy.combinatorics import Partition >>> Partition.from_rgs([0, 1, 2, 0, 1], list('abcde')) Partition({c}, {a, d}, {b, e}) >>> Partition.from_rgs([0, 1, 2, 0, 1], list('cbead')) Partition({e}, {a, c}, {b, d}) >>> a = Partition([1, 4], [2], [3, 5]) >>> Partition.from_rgs(a.RGS, a.members) Partition({2}, {1, 4}, {3, 5})
- property partition¶
Return partition as a sorted list of lists.
Examples
>>> from sympy.combinatorics import Partition >>> Partition([1], [2, 3]).partition [[1], [2, 3]]
- property rank¶
Gets the rank of a partition.
Examples
>>> from sympy.combinatorics import Partition >>> a = Partition([1, 2], [3], [4, 5]) >>> a.rank 13
- sort_key(order=None)[source]¶
Return a canonical key that can be used for sorting.
Ordering is based on the size and sorted elements of the partition and ties are broken with the rank.
Examples
>>> from sympy import default_sort_key >>> from sympy.combinatorics import Partition >>> from sympy.abc import x >>> a = Partition([1, 2]) >>> b = Partition([3, 4]) >>> c = Partition([1, x]) >>> d = Partition(list(range(4))) >>> l = [d, b, a + 1, a, c] >>> l.sort(key=default_sort_key); l [Partition({1, 2}), Partition({1}, {2}), Partition({1, x}), Partition({3, 4}), Partition({0, 1, 2, 3})]
- class sympy.combinatorics.partitions.IntegerPartition(partition, integer=None)[source]¶
This class represents an integer partition.
Explanation
In number theory and combinatorics, a partition of a positive integer,
n, also called an integer partition, is a way of writingnas a list of positive integers that sum to n. Two partitions that differ only in the order of summands are considered to be the same partition; if order matters then the partitions are referred to as compositions. For example, 4 has five partitions: [4], [3, 1], [2, 2], [2, 1, 1], and [1, 1, 1, 1]; the compositions [1, 2, 1] and [1, 1, 2] are the same as partition [2, 1, 1].References
- as_dict()[source]¶
Return the partition as a dictionary whose keys are the partition integers and the values are the multiplicity of that integer.
Examples
>>> from sympy.combinatorics.partitions import IntegerPartition >>> IntegerPartition([1]*3 + [2] + [3]*4).as_dict() {1: 3, 2: 1, 3: 4}
- as_ferrers(char='#')[source]¶
Prints the ferrer diagram of a partition.
Examples
>>> from sympy.combinatorics.partitions import IntegerPartition >>> print(IntegerPartition([1, 1, 5]).as_ferrers()) ##### # #
- property conjugate¶
Computes the conjugate partition of itself.
Examples
>>> from sympy.combinatorics.partitions import IntegerPartition >>> a = IntegerPartition([6, 3, 3, 2, 1]) >>> a.conjugate [5, 4, 3, 1, 1, 1]
- next_lex()[source]¶
Return the next partition of the integer, n, in lexical order, wrapping around to [n] if the partition is [1, …, 1].
Examples
>>> from sympy.combinatorics.partitions import IntegerPartition >>> p = IntegerPartition([3, 1]) >>> print(p.next_lex()) [4] >>> p.partition < p.next_lex().partition True
- prev_lex()[source]¶
Return the previous partition of the integer, n, in lexical order, wrapping around to [1, …, 1] if the partition is [n].
Examples
>>> from sympy.combinatorics.partitions import IntegerPartition >>> p = IntegerPartition([4]) >>> print(p.prev_lex()) [3, 1] >>> p.partition > p.prev_lex().partition True
- sympy.combinatorics.partitions.random_integer_partition(n, seed=None)[source]¶
Generates a random integer partition summing to
nas a list of reverse-sorted integers.Examples
>>> from sympy.combinatorics.partitions import random_integer_partition
For the following, a seed is given so a known value can be shown; in practice, the seed would not be given.
>>> random_integer_partition(100, seed=[1, 1, 12, 1, 2, 1, 85, 1]) [85, 12, 2, 1] >>> random_integer_partition(10, seed=[1, 2, 3, 1, 5, 1]) [5, 3, 1, 1] >>> random_integer_partition(1) [1]
- sympy.combinatorics.partitions.RGS_generalized(m)[source]¶
Computes the m + 1 generalized unrestricted growth strings and returns them as rows in matrix.
Examples
>>> from sympy.combinatorics.partitions import RGS_generalized >>> RGS_generalized(6) Matrix([ [ 1, 1, 1, 1, 1, 1, 1], [ 1, 2, 3, 4, 5, 6, 0], [ 2, 5, 10, 17, 26, 0, 0], [ 5, 15, 37, 77, 0, 0, 0], [ 15, 52, 151, 0, 0, 0, 0], [ 52, 203, 0, 0, 0, 0, 0], [203, 0, 0, 0, 0, 0, 0]])
- sympy.combinatorics.partitions.RGS_enum(m)[source]¶
RGS_enum computes the total number of restricted growth strings possible for a superset of size m.
Examples
>>> from sympy.combinatorics.partitions import RGS_enum >>> from sympy.combinatorics import Partition >>> RGS_enum(4) 15 >>> RGS_enum(5) 52 >>> RGS_enum(6) 203
We can check that the enumeration is correct by actually generating the partitions. Here, the 15 partitions of 4 items are generated:
>>> a = Partition(list(range(4))) >>> s = set() >>> for i in range(20): ... s.add(a) ... a += 1 ... >>> assert len(s) == 15