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_Complement  
is_EmptySet  
is_Intersection  
is_UniversalSet  
RGS

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
{{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.

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)
{{2}, {1, 4}, {3, 5}}
partition

Return partition as a sorted list of lists.

Examples

>>> from sympy.combinatorics.partitions import Partition
>>> Partition([1], [2, 3]).partition
[[1], [2, 3]]
rank

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

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
sympy.combinatorics.partitions.RGS_unrank(rank, m)[source]

Gives the unranked restricted growth string for a given superset size.

Examples

>>> from sympy.combinatorics.partitions import RGS_unrank
>>> RGS_unrank(14, 4)
[0, 1, 2, 3]
>>> RGS_unrank(0, 4)
[0, 0, 0, 0]
sympy.combinatorics.partitions.RGS_rank(rgs)[source]

Computes the rank of a restricted growth string.

Examples

>>> from sympy.combinatorics.partitions import RGS_rank, RGS_unrank
>>> RGS_rank([0, 1, 2, 1, 3])
42
>>> RGS_rank(RGS_unrank(4, 7))
4