Source code for sympy.combinatorics.partitions

from __future__ import print_function, division

from sympy.core import Basic, Dict, sympify
from sympy.core.compatibility import as_int, default_sort_key, range
from sympy.functions.combinatorial.numbers import bell
from sympy.matrices import zeros
from sympy.sets.sets import FiniteSet
from sympy.utilities.iterables import has_dups, flatten, group

from collections import defaultdict


[docs]class Partition(FiniteSet): """ This class represents an abstract partition. A partition is a set of disjoint sets whose union equals a given set. See Also ======== sympy.utilities.iterables.partitions, sympy.utilities.iterables.multiset_partitions """ _rank = None _partition = None def __new__(cls, *partition): """ Generates a new partition object. This method also verifies if the arguments passed are valid and raises a ValueError if they are not. Examples ======== >>> from sympy.combinatorics.partitions import Partition >>> a = Partition([1, 2], [3]) >>> a {{3}, {1, 2}} >>> a.partition [[1, 2], [3]] >>> len(a) 2 >>> a.members (1, 2, 3) """ args = partition if not all(isinstance(part, (list, FiniteSet)) for part in args): raise ValueError( "Each argument to Partition should be a list or a FiniteSet") # sort so we have a canonical reference for RGS partition = sorted(sum(partition, []), key=default_sort_key) if has_dups(partition): raise ValueError("Partition contained duplicated elements.") obj = FiniteSet.__new__(cls, *[FiniteSet(*x) for x in args]) obj.members = tuple(partition) obj.size = len(partition) return obj
[docs] def sort_key(self, order=None): """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}}] """ if order is None: members = self.members else: members = tuple(sorted(self.members, key=lambda w: default_sort_key(w, order))) return list(map(default_sort_key, (self.size, members, self.rank)))
@property def partition(self): """Return partition as a sorted list of lists. Examples ======== >>> from sympy.combinatorics.partitions import Partition >>> Partition([1], [2, 3]).partition [[1], [2, 3]] """ if self._partition is None: self._partition = sorted([sorted(p, key=default_sort_key) for p in self.args]) return self._partition def __add__(self, other): """ Return permutation whose rank is ``other`` greater than current rank, (mod the maximum rank for the set). Examples ======== >>> from sympy.combinatorics.partitions import Partition >>> a = Partition([1, 2], [3]) >>> a.rank 1 >>> (a + 1).rank 2 >>> (a + 100).rank 1 """ other = as_int(other) offset = self.rank + other result = RGS_unrank((offset) % RGS_enum(self.size), self.size) return Partition.from_rgs(result, self.members) def __sub__(self, other): """ Return permutation whose rank is ``other`` less than current rank, (mod the maximum rank for the set). Examples ======== >>> from sympy.combinatorics.partitions import Partition >>> a = Partition([1, 2], [3]) >>> a.rank 1 >>> (a - 1).rank 0 >>> (a - 100).rank 1 """ return self.__add__(-other) def __le__(self, other): """ Checks if a partition is less than or equal to the other based on rank. Examples ======== >>> from sympy.combinatorics.partitions import Partition >>> a = Partition([1, 2], [3, 4, 5]) >>> b = Partition([1], [2, 3], [4], [5]) >>> a.rank, b.rank (9, 34) >>> a <= a True >>> a <= b True """ return self.sort_key() <= sympify(other).sort_key() def __lt__(self, other): """ Checks if a partition is less than the other. Examples ======== >>> from sympy.combinatorics.partitions import Partition >>> a = Partition([1, 2], [3, 4, 5]) >>> b = Partition([1], [2, 3], [4], [5]) >>> a.rank, b.rank (9, 34) >>> a < b True """ return self.sort_key() < sympify(other).sort_key() @property def rank(self): """ Gets the rank of a partition. Examples ======== >>> from sympy.combinatorics.partitions import Partition >>> a = Partition([1, 2], [3], [4, 5]) >>> a.rank 13 """ if self._rank is not None: return self._rank self._rank = RGS_rank(self.RGS) return self._rank @property def RGS(self): """ 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) """ rgs = {} partition = self.partition for i, part in enumerate(partition): for j in part: rgs[j] = i return tuple([rgs[i] for i in sorted( [i for p in partition for i in p], key=default_sort_key)])
[docs] @classmethod def from_rgs(self, rgs, elements): """ 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}} """ if len(rgs) != len(elements): raise ValueError('mismatch in rgs and element lengths') max_elem = max(rgs) + 1 partition = [[] for i in range(max_elem)] j = 0 for i in rgs: partition[i].append(elements[j]) j += 1 if not all(p for p in partition): raise ValueError('some blocks of the partition were empty.') return Partition(*partition)
[docs]class IntegerPartition(Basic): """ 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 ======== sympy.utilities.iterables.partitions, sympy.utilities.iterables.multiset_partitions Reference: https://en.wikipedia.org/wiki/Partition_%28number_theory%29 """ _dict = None _keys = None def __new__(cls, partition, integer=None): """ Generates a new IntegerPartition object from a list or dictionary. The partition can be given as a list of positive integers or a dictionary of (integer, multiplicity) items. If the partition is preceded by an integer an error will be raised if the partition does not sum to that given integer. Examples ======== >>> from sympy.combinatorics.partitions import IntegerPartition >>> a = IntegerPartition([5, 4, 3, 1, 1]) >>> a IntegerPartition(14, (5, 4, 3, 1, 1)) >>> print(a) [5, 4, 3, 1, 1] >>> IntegerPartition({1:3, 2:1}) IntegerPartition(5, (2, 1, 1, 1)) If the value that the partition should sum to is given first, a check will be made to see n error will be raised if there is a discrepancy: >>> IntegerPartition(10, [5, 4, 3, 1]) Traceback (most recent call last): ... ValueError: The partition is not valid """ if integer is not None: integer, partition = partition, integer if isinstance(partition, (dict, Dict)): _ = [] for k, v in sorted(list(partition.items()), reverse=True): if not v: continue k, v = as_int(k), as_int(v) _.extend([k]*v) partition = tuple(_) else: partition = tuple(sorted(map(as_int, partition), reverse=True)) sum_ok = False if integer is None: integer = sum(partition) sum_ok = True else: integer = as_int(integer) if not sum_ok and sum(partition) != integer: raise ValueError("Partition did not add to %s" % integer) if any(i < 1 for i in partition): raise ValueError("The summands must all be positive.") obj = Basic.__new__(cls, integer, partition) obj.partition = list(partition) obj.integer = integer return obj
[docs] def prev_lex(self): """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 """ d = defaultdict(int) d.update(self.as_dict()) keys = self._keys if keys == [1]: return IntegerPartition({self.integer: 1}) if keys[-1] != 1: d[keys[-1]] -= 1 if keys[-1] == 2: d[1] = 2 else: d[keys[-1] - 1] = d[1] = 1 else: d[keys[-2]] -= 1 left = d[1] + keys[-2] new = keys[-2] d[1] = 0 while left: new -= 1 if left - new >= 0: d[new] += left//new left -= d[new]*new return IntegerPartition(self.integer, d)
[docs] def next_lex(self): """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 """ d = defaultdict(int) d.update(self.as_dict()) key = self._keys a = key[-1] if a == self.integer: d.clear() d[1] = self.integer elif a == 1: if d[a] > 1: d[a + 1] += 1 d[a] -= 2 else: b = key[-2] d[b + 1] += 1 d[1] = (d[b] - 1)*b d[b] = 0 else: if d[a] > 1: if len(key) == 1: d.clear() d[a + 1] = 1 d[1] = self.integer - a - 1 else: a1 = a + 1 d[a1] += 1 d[1] = d[a]*a - a1 d[a] = 0 else: b = key[-2] b1 = b + 1 d[b1] += 1 need = d[b]*b + d[a]*a - b1 d[a] = d[b] = 0 d[1] = need return IntegerPartition(self.integer, d)
[docs] def as_dict(self): """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} """ if self._dict is None: groups = group(self.partition, multiple=False) self._keys = [g[0] for g in groups] self._dict = dict(groups) return self._dict
@property def conjugate(self): """ 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] """ j = 1 temp_arr = list(self.partition) + [0] k = temp_arr[0] b = [0]*k while k > 0: while k > temp_arr[j]: b[k - 1] = j k -= 1 j += 1 return b def __lt__(self, other): """Return True if self is less than other when the partition is listed from smallest to biggest. Examples ======== >>> from sympy.combinatorics.partitions import IntegerPartition >>> a = IntegerPartition([3, 1]) >>> a < a False >>> b = a.next_lex() >>> a < b True >>> a == b False """ return list(reversed(self.partition)) < list(reversed(other.partition)) def __le__(self, other): """Return True if self is less than other when the partition is listed from smallest to biggest. Examples ======== >>> from sympy.combinatorics.partitions import IntegerPartition >>> a = IntegerPartition([4]) >>> a <= a True """ return list(reversed(self.partition)) <= list(reversed(other.partition))
[docs] def as_ferrers(self, char='#'): """ Prints the ferrer diagram of a partition. Examples ======== >>> from sympy.combinatorics.partitions import IntegerPartition >>> print(IntegerPartition([1, 1, 5]).as_ferrers()) ##### # # """ return "\n".join([char*i for i in self.partition])
def __str__(self): return str(list(self.partition))
[docs]def random_integer_partition(n, seed=None): """ 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] """ from sympy.utilities.randtest import _randint n = as_int(n) if n < 1: raise ValueError('n must be a positive integer') randint = _randint(seed) partition = [] while (n > 0): k = randint(1, n) mult = randint(1, n//k) partition.append((k, mult)) n -= k*mult partition.sort(reverse=True) partition = flatten([[k]*m for k, m in partition]) return partition
[docs]def RGS_generalized(m): """ 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]]) """ d = zeros(m + 1) for i in range(0, m + 1): d[0, i] = 1 for i in range(1, m + 1): for j in range(m): if j <= m - i: d[i, j] = j * d[i - 1, j] + d[i - 1, j + 1] else: d[i, j] = 0 return d
[docs]def RGS_enum(m): """ 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 """ if (m < 1): return 0 elif (m == 1): return 1 else: return bell(m)
[docs]def RGS_unrank(rank, m): """ 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] """ if m < 1: raise ValueError("The superset size must be >= 1") if rank < 0 or RGS_enum(m) <= rank: raise ValueError("Invalid arguments") L = [1] * (m + 1) j = 1 D = RGS_generalized(m) for i in range(2, m + 1): v = D[m - i, j] cr = j*v if cr <= rank: L[i] = j + 1 rank -= cr j += 1 else: L[i] = int(rank / v + 1) rank %= v return [x - 1 for x in L[1:]]
[docs]def RGS_rank(rgs): """ 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 """ rgs_size = len(rgs) rank = 0 D = RGS_generalized(rgs_size) for i in range(1, rgs_size): n = len(rgs[(i + 1):]) m = max(rgs[0:i]) rank += D[n, m + 1] * rgs[i] return rank