Coverage for local/lib/python2.7/site-packages/sage/combinat/set_partition.py : 75%

r""" 

Set Partitions 

AUTHORS: 

- Mike Hansen 

- MuPAD-Combinat developers (for algorithms and design inspiration). 

- Travis Scrimshaw (2013-02-28): Removed ``CombinatorialClass`` and added 

entry point through :class:`SetPartition`. 

- Martin Rubey (2017-10-10): Cleanup, add crossings and nestings, add 

random generation. 

This module defines a class for immutable partitioning of a set. For 

mutable version see :func:`DisjointSet`. 

""" 

#***************************************************************************** 

# Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>, 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# 

# This code is distributed in the hope that it will be useful, 

# but WITHOUT ANY WARRANTY; without even the implied warranty of 

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 

# General Public License for more details. 

# 

# The full text of the GPL is available at: 

# 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from __future__ import print_function, absolute_import, division 

from six.moves import range 

from six import add_metaclass 

from sage.sets.set import Set, Set_generic 

import itertools 

from sage.structure.parent import Parent 

from sage.structure.unique_representation import UniqueRepresentation 

from sage.structure.list_clone import ClonableArray 

from sage.categories.infinite_enumerated_sets import InfiniteEnumeratedSets 

from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets 

from sage.misc.inherit_comparison import InheritComparisonClasscallMetaclass 

from sage.rings.infinity import infinity 

from sage.rings.integer import Integer 

from sage.combinat.misc import IterableFunctionCall 

from sage.combinat.combinatorial_map import combinatorial_map 

import sage.combinat.subset as subset 

from sage.combinat.partition import Partition, Partitions 

from sage.combinat.set_partition_ordered import OrderedSetPartitions 

from sage.combinat.combinat import bell_number, stirling_number2 

from sage.combinat.permutation import Permutation 

from sage.functions.other import factorial 

from sage.misc.prandom import random, randint 

from sage.probability.probability_distribution import GeneralDiscreteDistribution 

@add_metaclass(InheritComparisonClasscallMetaclass) 

class SetPartition(ClonableArray): 

""" 

A partition of a set. 

A set partition `p` of a set `S` is a partition of `S` into subsets 

called parts and represented as a set of sets. By extension, a set 

partition of a nonnegative integer `n` is the set partition of the 

integers from 1 to `n`. The number of set partitions of `n` is called 

the `n`-th Bell number. 

There is a natural integer partition associated with a set partition, 

namely the nonincreasing sequence of sizes of all its parts. 

There is a classical lattice associated with all set partitions of 

`n`. The infimum of two set partitions is the set partition obtained 

by intersecting all the parts of both set partitions. The supremum 

is obtained by transitive closure of the relation `i` related to `j` 

if and only if they are in the same part in at least one of the set 

partitions. 

We will use terminology from partitions, in particular the *length* of 

a set partition `A = \{A_1, \ldots, A_k\}` is the number of parts of `A` 

and is denoted by `|A| := k`. The *size* of `A` is the cardinality of `S`. 

We will also sometimes use the notation `[n] := \{1, 2, \ldots, n\}`. 

EXAMPLES: 

There are 5 set partitions of the set `\{1,2,3\}`:: 

sage: SetPartitions(3).cardinality() 

5 

Here is the list of them:: 

sage: SetPartitions(3).list() 

[{{1, 2, 3}}, 

{{1}, {2, 3}}, 

{{1, 3}, {2}}, 

{{1, 2}, {3}}, 

{{1}, {2}, {3}}] 

There are 6 set partitions of `\{1,2,3,4\}` whose underlying partition is 

`[2, 1, 1]`:: 

sage: SetPartitions(4, [2,1,1]).list() 

[{{1}, {2}, {3, 4}}, 

{{1}, {2, 4}, {3}}, 

{{1}, {2, 3}, {4}}, 

{{1, 4}, {2}, {3}}, 

{{1, 3}, {2}, {4}}, 

{{1, 2}, {3}, {4}}] 

Since :trac:`14140`, we can create a set partition directly by 

:class:`SetPartition`, which creates the base set by taking the 

union of the parts passed in:: 

sage: s = SetPartition([[1,3],[2,4]]); s 

{{1, 3}, {2, 4}} 

sage: s.parent() 

Set partitions 

""" 

@staticmethod 

def __classcall_private__(cls, parts, check=True): 

""" 

Create a set partition from ``parts`` with the appropriate parent. 

EXAMPLES:: 

sage: s = SetPartition([[1,3],[2,4]]); s 

{{1, 3}, {2, 4}} 

sage: s.parent() 

Set partitions 

""" 

P = SetPartitions() 

return P.element_class(P, parts, check=check) 

def __init__(self, parent, s, check=True): 

""" 

Initialize ``self``. 

EXAMPLES:: 

sage: S = SetPartitions(4) 

sage: s = S([[1,3],[2,4]]) 

sage: TestSuite(s).run() 

sage: SetPartition([]) 

{} 

""" 

self._latex_options = {} 

ClonableArray.__init__(self, parent, sorted(map(Set, s), key=min), check=check) 

def check(self): 

""" 

Check that we are a valid set partition. 

EXAMPLES:: 

sage: S = SetPartitions(4) 

sage: s = S([[1, 3], [2, 4]]) 

sage: s.check() 

TESTS:: 

sage: s = S([[1, 2, 3]], check=False) 

sage: s.check() 

Traceback (most recent call last): 

... 

ValueError: {{1, 2, 3}} is not an element of Set partitions of {1, 2, 3, 4} 

sage: s = S([1, 2, 3]) 

Traceback (most recent call last): 

... 

TypeError: Element has no defined underlying set 

""" 

if self not in self.parent(): 

raise ValueError("%s is not an element of %s"%(self, self.parent())) 

def __hash__(self): 

""" 

Return the hash of ``self``. 

The parent is not included as part of the hash. 

EXAMPLES:: 

sage: P = SetPartitions(4) 

sage: A = SetPartition([[1], [2,3], [4]]) 

sage: B = P([[1], [2,3], [4]]) 

sage: hash(A) == hash(B) 

True 

""" 

return sum(hash(x) for x in self) 

def __eq__(self, y): 

""" 

Check equality of ``self`` and ``y``. 

The parent is not included as part of the equality check. 

EXAMPLES:: 

sage: P = SetPartitions(4) 

sage: A = SetPartition([[1], [2,3], [4]]) 

sage: B = P([[1], [2,3], [4]]) 

sage: A == B 

True 

sage: C = P([[2, 3], [1], [4]]) 

sage: A == C 

True 

sage: D = P([[1], [2, 4], [3]]) 

sage: A == D 

False 

""" 

if not isinstance(y, SetPartition): 

return False 

return list(self) == list(y) 

def __ne__(self, y): 

""" 

Check lack of equality of ``self`` and ``y``. 

The parent is not included as part of the equality check. 

EXAMPLES:: 

sage: P = SetPartitions(4) 

sage: A = SetPartition([[1], [2,3], [4]]) 

sage: B = P([[1], [2,3], [4]]) 

sage: A != B 

False 

sage: C = P([[2, 3], [1], [4]]) 

sage: A != C 

False 

sage: D = P([[1], [2, 4], [3]]) 

sage: A != D 

True 

""" 

return not (self == y) 

def __lt__(self, y): 

""" 

Check that ``self`` is less than ``y``. 

The ordering used is lexicographic, where: 

- a set partition is considered as the list of its parts 

sorted by increasing smallest element; 

- each part is regarded as a list of its elements, sorted 

in increasing order; 

- the parts themselves are compared lexicographically. 

EXAMPLES:: 

sage: P = SetPartitions(4) 

sage: A = P([[1], [2,3], [4]]) 

sage: B = SetPartition([[1,2,3], [4]]) 

sage: A < B 

True 

sage: C = P([[1,2,4], [3]]) 

sage: B < C 

True 

sage: B < B 

False 

sage: D = P([[1,4], [2], [3]]) 

sage: E = P([[1,4], [2,3]]) 

sage: D < E 

True 

sage: F = P([[1,2,4], [3]]) 

sage: E < C 

False 

sage: A < E 

True 

sage: A < C 

True 

""" 

if not isinstance(y, SetPartition): 

return False 

return [sorted(_) for _ in self] < [sorted(_) for _ in y] 

def __gt__(self, y): 

""" 

Check that ``self`` is greater than ``y``. 

The ordering used is lexicographic, where: 

- a set partition is considered as the list of its parts 

sorted by increasing smallest element; 

- each part is regarded as a list of its elements, sorted 

in increasing order; 

- the parts themselves are compared lexicographically. 

EXAMPLES:: 

sage: P = SetPartitions(4) 

sage: A = P([[1], [2,3], [4]]) 

sage: B = SetPartition([[1,2,3], [4]]) 

sage: B > A 

True 

sage: A > B 

False 

""" 

if not isinstance(y, SetPartition): 

return False 

return [sorted(_) for _ in self] > [sorted(_) for _ in y] 

def __le__(self, y): 

""" 

Check that ``self`` is less than or equals ``y``. 

The ordering used is lexicographic, where: 

- a set partition is considered as the list of its parts 

sorted by increasing smallest element; 

- each part is regarded as a list of its elements, sorted 

in increasing order; 

- the parts themselves are compared lexicographically. 

EXAMPLES:: 

sage: P = SetPartitions(4) 

sage: A = P([[1], [2,3], [4]]) 

sage: B = SetPartition([[1,2,3], [4]]) 

sage: A <= B 

True 

sage: A <= A 

True 

""" 

return self == y or self < y 

def __ge__(self, y): 

""" 

Check that ``self`` is greater than or equals ``y``. 

The ordering used is lexicographic, where: 

- a set partition is considered as the list of its parts 

sorted by increasing smallest element; 

- each part is regarded as a list of its elements, sorted 

in increasing order; 

- the parts themselves are compared lexicographically. 

EXAMPLES:: 

sage: P = SetPartitions(4) 

sage: A = P([[1], [2,3], [4]]) 

sage: B = SetPartition([[1,2,3], [4]]) 

sage: B >= A 

True 

sage: B >= B 

True 

""" 

return self == y or self > y 

def __mul__(self, other): 

r""" 

The product of the set partitions ``self`` and ``other``. 

The product of two set partitions `B` and `C` is defined as the 

set partition whose parts are the nonempty intersections between 

each part of `B` and each part of `C`. This product is also 

the infimum of `B` and `C` in the classical set partition 

lattice (that is, the coarsest set partition which is finer than 

each of `B` and `C`). Consequently, ``inf`` acts as an alias for 

this method. 

.. SEEALSO:: 

:meth:`sup` 

EXAMPLES:: 

sage: x = SetPartition([ [1,2], [3,5,4] ]) 

sage: y = SetPartition(( (3,1,2), (5,4) )) 

sage: x * y 

{{1, 2}, {3}, {4, 5}} 

sage: S = SetPartitions(4) 

sage: sp1 = S([[2,3,4], [1]]) 

sage: sp2 = S([[1,3], [2,4]]) 

sage: s = S([[2,4], [3], [1]]) 

sage: sp1.inf(sp2) == s 

True 

TESTS: 

Here is a different implementation of the ``__mul__`` method 

(one that was formerly used for the ``inf`` method, before it 

was realized that the methods do the same thing):: 

sage: def mul2(s, t): 

....: temp = [ss.intersection(ts) for ss in s for ts in t] 

....: temp = filter(lambda x: x != Set([]), temp) 

....: return s.__class__(s.parent(), temp) 

Let us check that this gives the same as ``__mul__`` on set 

partitions of `\{1, 2, 3, 4\}`:: 

sage: all( all( mul2(s, t) == s * t for s in SetPartitions(4) ) 

....: for t in SetPartitions(4) ) 

True 

""" 

new_composition = [] 

for B in self: 

for C in other: 

BintC = B.intersection(C) 

if BintC: 

new_composition.append(BintC) 

return SetPartition(new_composition) 

inf = __mul__ 

def _repr_(self): 

""" 

Return a string representation of ``self``. 

EXAMPLES:: 

sage: S = SetPartitions(4) 

sage: S([[1,3],[2,4]]) 

{{1, 3}, {2, 4}} 

""" 

return '{' + ', '.join(('{' + repr(sorted(x))[1:-1] + '}' for x in self)) + '}' 

def set_latex_options(self, **kwargs): 

r""" 

Set the latex options for use in the ``_latex_`` function 

- ``tikz_scale`` -- (default: 1) scale for use with tikz package 

- ``plot`` -- (default: ``None``) ``None`` returns the set notation, 

``linear`` returns a linear plot, ``cyclic`` returns a cyclic 

plot 

- ``color`` -- (default: ``'black'``) the arc colors 

- ``fill`` -- (default: ``False``) if ``True`` then fills ``color``, 

else you can pass in a color to alter the fill color - 

*only works with cyclic plot* 

- ``show_labels`` -- (default: ``True``) if ``True`` shows labels - 

*only works with plots* 

- ``radius`` -- (default: ``"1cm"``) radius of circle for cyclic 

plot - *only works with cyclic plot* 

- ``angle`` -- (default: 0) angle for linear plot 

EXAMPLES:: 

sage: SP = SetPartition([[1,6], [3,5,4]]) 

sage: SP.set_latex_options(tikz_scale=2,plot='linear',fill=True,color='blue',angle=45) 

sage: SP.set_latex_options(plot='cyclic') 

sage: SP.latex_options() 

{'angle': 45, 

'color': 'blue', 

'fill': True, 

'plot': 'cyclic', 

'radius': '1cm', 

'show_labels': True, 

'tikz_scale': 2} 

""" 

valid_args = ['tikz_scale', 'plot', 'color', 'fill', 'show_labels', 

'radius', 'angle'] 

for key in kwargs: 

if key not in valid_args: 

raise ValueError("unknown keyword argument: %s"%key) 

if key == 'plot': 

if not (kwargs['plot'] == 'cyclic' 

or kwargs['plot'] == 'linear' 

or kwargs['plot'] is None): 

raise ValueError("plot must be None, 'cyclic', or 'linear'") 

for opt in kwargs: 

self._latex_options[opt] = kwargs[opt] 

def latex_options(self): 

r""" 

Return the latex options for use in the ``_latex_`` function as a 

dictionary. The default values are set using the global options. 

Options can be found in :meth:`set_latex_options` 

EXAMPLES:: 

sage: SP = SetPartition([[1,6], [3,5,4]]); SP.latex_options() 

{'angle': 0, 

'color': 'black', 

'fill': False, 

'plot': None, 

'radius': '1cm', 

'show_labels': True, 

'tikz_scale': 1} 

""" 

opts = self._latex_options.copy() 

if "tikz_scale" not in opts: 

opts["tikz_scale"] = 1 

if "plot" not in opts: 

opts["plot"] = None 

if "color" not in opts: 

opts['color'] = 'black' 

if "fill" not in opts: 

opts["fill"] = False 

if "show_labels" not in opts: 

opts['show_labels'] = True 

if "radius" not in opts: 

opts['radius'] = "1cm" 

if "angle" not in opts: 

opts['angle'] = 0 

return opts 

def _latex_(self): 

r""" 

Return a `\LaTeX` string representation of ``self``. 

EXAMPLES:: 

sage: x = SetPartition([[1,2], [3,5,4]]) 

sage: latex(x) 

\{\{1, 2\}, \{3, 4, 5\}\} 

sage: x.set_latex_options(plot='linear', angle=25, color='red') 

sage: latex(x) 

\begin{tikzpicture}[scale=1] 

\node[below=.05cm] at (0,0) {$1$}; 

\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (0) at (0,0) {}; 

\node[below=.05cm] at (1,0) {$2$}; 

\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (1,0) {}; 

\node[below=.05cm] at (2,0) {$3$}; 

\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (2,0) {}; 

\node[below=.05cm] at (3,0) {$4$}; 

\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (3,0) {}; 

\node[below=.05cm] at (4,0) {$5$}; 

\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (4,0) {}; 

\draw[color=red] (1) to [out=115,in=65] (0); 

\draw[color=red] (3) to [out=115,in=65] (2); 

\draw[color=red] (4) to [out=115,in=65] (3); 

\end{tikzpicture} 

sage: p = SetPartition([['a','c'],['b',1],[20]]) 

sage: p.set_latex_options(plot='cyclic', color='blue', fill=True, tikz_scale=2) 

sage: latex(p) 

\begin{tikzpicture}[scale=2] 

\draw (0,0) circle [radius=1cm]; 

\node[label=90:1] (0) at (90:1cm) {}; 

\node[label=18:20] (1) at (18:1cm) {}; 

\node[label=-54:a] (2) at (-54:1cm) {}; 

\node[label=-126:b] (3) at (-126:1cm) {}; 

\node[label=-198:c] (4) at (-198:1cm) {}; 

\draw[-,thick,color=blue,fill=blue,fill opacity=0.1] (2.center) -- (4.center) -- cycle; 

\draw[-,thick,color=blue,fill=blue,fill opacity=0.1] (0.center) -- (3.center) -- cycle; 

\draw[-,thick,color=blue,fill=blue,fill opacity=0.1] (1.center) -- cycle; 

\fill[color=black] (0) circle (1.5pt); 

\fill[color=black] (1) circle (1.5pt); 

\fill[color=black] (2) circle (1.5pt); 

\fill[color=black] (3) circle (1.5pt); 

\fill[color=black] (4) circle (1.5pt); 

\end{tikzpicture} 

""" 

latex_options = self.latex_options() 

if latex_options["plot"] is None: 

return repr(self).replace("{",r"\{").replace("}",r"\}") 

from sage.misc.latex import latex 

latex.add_package_to_preamble_if_available("tikz") 

res = "\\begin{{tikzpicture}}[scale={}]\n".format(latex_options['tikz_scale']) 

cardinality = self.base_set_cardinality() 

from sage.rings.integer_ring import ZZ 

if all(x in ZZ for x in self.base_set()): 

sort_key = ZZ 

else: 

sort_key = str 

base_set = sorted(self.base_set(), key=sort_key) 

color = latex_options['color'] 

# If we want cyclic plots 

if latex_options['plot'] == 'cyclic': 

degrees = 360 // cardinality 

radius = latex_options['radius'] 

res += "\\draw (0,0) circle [radius={}];\n".format(radius) 

# Add nodes 

for k,i in enumerate(base_set): 

location = (cardinality - k) * degrees - 270 

if latex_options['show_labels']: 

res += "\\node[label={}:{}]".format(location, i) 

else: 

res += "\\node" 

res += " ({}) at ({}:{}) {{}};\n".format(k, location, radius) 

# Setup partitions 

for partition in sorted(self, key=str): 

res += "\\draw[-,thick,color="+color 

if latex_options['fill'] is not False: 

if isinstance(latex_options['fill'], str): 

res += ",fill=" + latex_options['fill'] 

else: 

res += ",fill={},fill opacity=0.1".format(color) 

res += "] " 

res += " -- ".join("({}.center)".format(base_set.index(j)) 

for j in sorted(partition, key=sort_key)) 

res += " -- cycle;\n" 

# Draw the circles on top 

for k in range(len(base_set)): 

res += "\\fill[color=black] ({}) circle (1.5pt);\n".format(k) 

# If we want line plots 

elif latex_options['plot'] == 'linear': 

angle = latex_options['angle'] 

# setup line 

for k,i in enumerate(base_set): 

if latex_options['show_labels']: 

res += "\\node[below=.05cm] at ({},0) {{${}$}};\n".format(k, i) 

res += "\\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] " 

res += "({k}) at ({k},0) {{}};\n".format(k=k) 

# setup arcs 

for partition in sorted(self, key=str): 

p = sorted(partition, key=sort_key) 

if len(p) <= 1: 

continue 

for k in range(1, len(p)): 

res += "\\draw[color={}] ({})".format(color, base_set.index(p[k])) 

res += " to [out={},in={}] ".format(90+angle, 90-angle) 

res += "({});\n".format(base_set.index(p[k-1])) 

else: 

raise ValueError("plot must be None, 'cyclic', or 'linear'") 

res += "\\end{tikzpicture}" 

return res 

cardinality = ClonableArray.__len__ 

def sup(self, t): 

""" 

Return the supremum of ``self`` and ``t`` in the classical set 

partition lattice. 

The supremum of two set partitions `B` and `C` is obtained as the 

transitive closure of the relation which relates `i` to `j` if 

and only if `i` and `j` are in the same part in at least 

one of the set partitions `B` and `C`. 

.. SEEALSO:: 

:meth:`__mul__` 

EXAMPLES:: 

sage: S = SetPartitions(4) 

sage: sp1 = S([[2,3,4], [1]]) 

sage: sp2 = S([[1,3], [2,4]]) 

sage: s = S([[1,2,3,4]]) 

sage: sp1.sup(sp2) == s 

True 

""" 

res = Set(list(self)) 

for p in t: 

inters = Set([x for x in list(res) if x.intersection(p) != Set([])]) 

res = res.difference(inters).union(_set_union(inters)) 

return SetPartition(res) 

def pipe(self, other): 

r""" 

Return the pipe of the set partitions ``self`` and ``other``. 

The pipe of two set partitions is defined as follows: 

For any integer `k` and any subset `I` of `\ZZ`, let `I + k` 

denote the subset of `\ZZ` obtained by adding `k` to every 

element of `k`. 

If `B` and `C` are set partitions of `[n]` and `[m]`, 

respectively, then the pipe of `B` and `C` is defined as the 

set partition 

.. MATH:: 

\{ B_1, B_2, \ldots, B_b, 

C_1 + n, C_2 + n, \ldots, C_c + n \} 

of `[n+m]`, where `B = \{ B_1, B_2, \ldots, B_b \}` and 

`C = \{ C_1, C_2, \ldots, C_c \}`. This pipe is denoted by 

`B | C`. 

EXAMPLES:: 

sage: SetPartition([[1,3],[2,4]]).pipe(SetPartition([[1,3],[2]])) 

{{1, 3}, {2, 4}, {5, 7}, {6}} 

sage: SetPartition([]).pipe(SetPartition([[1,2],[3,5],[4]])) 

{{1, 2}, {3, 5}, {4}} 

sage: SetPartition([[1,2],[3,5],[4]]).pipe(SetPartition([])) 

{{1, 2}, {3, 5}, {4}} 

sage: SetPartition([[1,2],[3]]).pipe(SetPartition([[1]])) 

{{1, 2}, {3}, {4}} 

""" 

# Note: GIGO if self and other are not standard. 

parts = list(self) 

n = self.base_set_cardinality() 

for newpart in other: 

raised_newpart = Set([i + n for i in newpart]) 

parts.append(raised_newpart) 

return SetPartition(parts) 

@combinatorial_map(name='shape') 

def shape(self): 

r""" 

Return the integer partition whose parts are the sizes of the sets 

in ``self``. 

EXAMPLES:: 

sage: S = SetPartitions(5) 

sage: x = S([[1,2], [3,5,4]]) 

sage: x.shape() 

[3, 2] 

sage: y = S([[2], [3,1], [5,4]]) 

sage: y.shape() 

[2, 2, 1] 

""" 

return Partition(sorted(map(len, self), reverse=True)) 

# we define aliases for shape() 

shape_partition = shape 

to_partition = shape 

@combinatorial_map(name='to permutation') 

def to_permutation(self): 

r""" 

Convert a set partition of `\{1,...,n\}` to a permutation by considering 

the blocks of the partition as cycles. 

The cycles are such that the number of excedences is maximised, that is, 

each cycle is of the form `(a_1,a_2, ...,a_k)` with `a_1<a_2<...<a_k`. 

EXAMPLES:: 

sage: s = SetPartition([[1,3],[2,4]]) 

sage: s.to_permutation()