Partitions

class diofant.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.

See also

diofant.utilities.iterables.partitions, diofant.utilities.iterables.multiset_partitions

property 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

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

>>> 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}}
property partition

Return partition as a sorted list of lists.

Examples

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

Gets the rank of a partition.

Examples

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

>>> 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 diofant.combinatorics.partitions.IntegerPartition(partition, integer=None)[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].

See also

diofant.utilities.iterables.partitions, diofant.utilities.iterables.multiset_partitions

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

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

>>> print(IntegerPartition([1, 1, 5]).as_ferrers())
#####
#
#
property conjugate

Computes the conjugate partition of itself.

Examples

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

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

>>> p = IntegerPartition([4])
>>> print(p.prev_lex())
[3, 1]
>>> p.partition > p.prev_lex().partition
True
diofant.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

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]
diofant.combinatorics.partitions.RGS_generalized(m)[source]

Computes the m + 1 generalized unrestricted growth strings and returns them as rows in matrix.

Examples

>>> 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]])
diofant.combinatorics.partitions.RGS_enum(m)[source]

RGS_enum computes the total number of restricted growth strings possible for a superset of size m.

Examples

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

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

Examples

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

Computes the rank of a restricted growth string.

Examples

>>> RGS_rank([0, 1, 2, 1, 3])
42
>>> RGS_rank(RGS_unrank(4, 7))
4