Partitions¶
- class sympy.combinatorics.partitions.Partition[source]¶
This class represents an abstract partition.
A partition is a set of disjoint sets whose union equals a given set.
Attributes
is_EmptySet is_Intersection is_UniversalSet - RGS[source]¶
Returns the “restricted growth string” of the partition.
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.partitions 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 {{1, 2}, {3}, {4}, {5}} >>> _.RGS (0, 0, 1, 2, 3)
- classmethod from_rgs(rgs, elements)[source]¶
Creates a set partition from a restricted growth string.
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 rgs an error will be raised.
Examples
>>> from sympy.combinatorics.partitions import Partition >>> Partition.from_rgs([0, 1, 2, 0, 1], list('abcde')) {{c}, {a, d}, {b, e}} >>> Partition.from_rgs([0, 1, 2, 0, 1], list('cbead')) {{e}, {a, c}, {b, d}} >>> a = Partition([[1, 4], [2], [3, 5]]) >>> Partition.from_rgs(a.RGS, a.members) {{1, 4}, {2}, {3, 5}}
- partition[source]¶
Return partition as a sorted list of lists.
Examples
>>> from sympy.combinatorics.partitions import Partition >>> Partition([[1], [2, 3]]).partition [[1], [2, 3]]
- rank[source]¶
Gets the rank of a partition.
Examples
>>> from sympy.combinatorics.partitions 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.utilities.iterables import default_sort_key >>> from sympy.combinatorics.partitions 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 [{{1, 2}}, {{1}, {2}}, {{1, x}}, {{3, 4}}, {{0, 1, 2, 3}}]
- class sympy.combinatorics.partitions.IntegerPartition[source]¶
This class represents an integer partition.
In number theory and combinatorics, a partition of a positive integer, n, also called an integer partition, is a way of writing n as 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].
- 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()) ##### # #
- conjugate[source]¶
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 n as 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.partitions 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
