Coverage for local/lib/python2.7/site-packages/sage/combinat/partition

Set partitions of {1, ..., 3, -1, ..., -3} with 3 and -3 in the same block and with at most 1 positive and negative entry in each block and that are planar

"""

return SetPartitionsRkhalf_k._repr_(self) + " and that are planar"

def cardinality(self):

"""

TESTS::

sage: SetPartitionsPRk(2.5).cardinality()

sage: SetPartitionsPRk(3.5).cardinality()

sage: SetPartitionsPRk(4.5).cardinality()

"""

return binomial(2*self.k, self.k)

def __iter__(self):

"""

TESTS::

sage: L = list(SetPartitionsPRk(2.5)); L

[{{-3, 3}, {-2}, {-1}, {1}, {2}}, {{-3, 3}, {-2}, {-1, 1}, {2}},

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

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

sage: len(L)

"""

positives = Set(range(1, self.k+1))

negatives = Set( [ -i for i in positives ] )

yield self.element_class(self, to_set_partition([[self.k+1, -self.k-1]],k=self.k+1))

for n in range(1,self.k+1):

for top in Subsets(positives, n):

t = sorted(top)

for bottom in Subsets(negatives, n):

b = list(bottom)

b.sort(reverse=True)

l = [ [t[i], b[ i ] ] for i in range(n) ] + [ [self.k+1, -self.k-1] ]

yield self.element_class(self, to_set_partition(l, k=self.k+1))

#########################################################

#Algebras

class PartitionAlgebra_generic(CombinatorialAlgebra):

def __init__(self, R, cclass, n, k, name=None, prefix=None):

"""

EXAMPLES::

sage: from sage.combinat.partition_algebra import *

sage: s = PartitionAlgebra_sk(QQ, 3, 1)

sage: s == loads(dumps(s))

True

"""

self.k = k

self.n = n

self._indices = cclass

self._name = "Generic partition algebra with k = %s and n = %s and basis %s"%( self.k, self.n, cclass) if name is None else name

self._one = identity(ceil(self.k))

self._prefix = "" if prefix is None else prefix

CombinatorialAlgebra.__init__(self, R)

def _multiply_basis(self, left, right):

"""

EXAMPLES::

sage: from sage.combinat.partition_algebra import *

sage: s = PartitionAlgebra_sk(QQ, 3, 1)

sage: t12 = s(Set([Set([1,-2]),Set([2,-1]),Set([3,-3])]))

sage: t12^2 == s(1) #indirect doctest

True

"""

(sp, l) = set_partition_composition(left, right)

return {sp: self.n**l}

class PartitionAlgebraElement_generic(CombinatorialAlgebraElement):

pass

class PartitionAlgebraElement_ak(PartitionAlgebraElement_generic):

pass

class PartitionAlgebra_ak(PartitionAlgebra_generic):

def __init__(self, R, k, n, name=None):

"""

EXAMPLES::

sage: from sage.combinat.partition_algebra import *

sage: p = PartitionAlgebra_ak(QQ, 3, 1)

sage: p == loads(dumps(p))

True

"""

if name is None:

name = "Partition algebra A_%s(%s)"%(k, n)

cclass = SetPartitionsAk(k)

self._element_class = PartitionAlgebraElement_ak

PartitionAlgebra_generic.__init__(self, R, cclass, n, k, name=name, prefix="A")

class PartitionAlgebraElement_bk(PartitionAlgebraElement_generic):

pass

class PartitionAlgebra_bk(PartitionAlgebra_generic):

def __init__(self, R, k, n, name=None):

"""

EXAMPLES::

sage: from sage.combinat.partition_algebra import *

sage: p = PartitionAlgebra_bk(QQ, 3, 1)

sage: p == loads(dumps(p))

True

"""

if name is None:

name = "Partition algebra B_%s(%s)"%(k, n)

cclass = SetPartitionsBk(k)

self._element_class = PartitionAlgebraElement_bk

PartitionAlgebra_generic.__init__(self, R, cclass, n, k, name=name, prefix="B")

class PartitionAlgebraElement_sk(PartitionAlgebraElement_generic):

pass

class PartitionAlgebra_sk(PartitionAlgebra_generic):

def __init__(self, R, k, n, name=None):

"""

EXAMPLES::

sage: from sage.combinat.partition_algebra import *

sage: p = PartitionAlgebra_sk(QQ, 3, 1)

sage: p == loads(dumps(p))

True

"""

if name is None:

name = "Partition algebra S_%s(%s)"%(k, n)

cclass = SetPartitionsSk(k)

self._element_class = PartitionAlgebraElement_sk

PartitionAlgebra_generic.__init__(self, R, cclass, n, k, name=name, prefix="S")

class PartitionAlgebraElement_pk(PartitionAlgebraElement_generic):

pass

class PartitionAlgebra_pk(PartitionAlgebra_generic):

def __init__(self, R, k, n, name=None):

"""

EXAMPLES::

sage: from sage.combinat.partition_algebra import *

sage: p = PartitionAlgebra_pk(QQ, 3, 1)

sage: p == loads(dumps(p))

True

"""

if name is None:

name = "Partition algebra P_%s(%s)"%(k, n)

cclass = SetPartitionsPk(k)

self._element_class = PartitionAlgebraElement_pk

PartitionAlgebra_generic.__init__(self, R, cclass, n, k, name=name, prefix="P")

class PartitionAlgebraElement_tk(PartitionAlgebraElement_generic):

pass

class PartitionAlgebra_tk(PartitionAlgebra_generic):

def __init__(self, R, k, n, name=None):

"""

EXAMPLES::

sage: from sage.combinat.partition_algebra import *

sage: p = PartitionAlgebra_tk(QQ, 3, 1)

sage: p == loads(dumps(p))

True

"""

if name is None:

name = "Partition algebra T_%s(%s)"%(k, n)

cclass = SetPartitionsTk(k)

self._element_class = PartitionAlgebraElement_tk

PartitionAlgebra_generic.__init__(self, R, cclass, n, k, name=name, prefix="T")

class PartitionAlgebraElement_rk(PartitionAlgebraElement_generic):

pass

class PartitionAlgebra_rk(PartitionAlgebra_generic):

def __init__(self, R, k, n, name=None):

"""

EXAMPLES::

sage: from sage.combinat.partition_algebra import *

sage: p = PartitionAlgebra_rk(QQ, 3, 1)

sage: p == loads(dumps(p))

True

"""

if name is None:

name = "Partition algebra R_%s(%s)"%(k, n)

cclass = SetPartitionsRk(k)

self._element_class = PartitionAlgebraElement_rk

PartitionAlgebra_generic.__init__(self, R, cclass, n, k, name=name, prefix="R")

class PartitionAlgebraElement_prk(PartitionAlgebraElement_generic):

pass

class PartitionAlgebra_prk(PartitionAlgebra_generic):

def __init__(self, R, k, n, name=None):

"""

EXAMPLES::

sage: from sage.combinat.partition_algebra import *

sage: p = PartitionAlgebra_prk(QQ, 3, 1)

sage: p == loads(dumps(p))

True

"""

if name is None:

name = "Partition algebra PR_%s(%s)"%(k, n)

cclass = SetPartitionsPRk(k)

self._element_class = PartitionAlgebraElement_prk

PartitionAlgebra_generic.__init__(self, R, cclass, n, k, name=name, prefix="PR")

##########################################################

def is_planar(sp):

"""

Returns True if the diagram corresponding to the set partition is

planar; otherwise, it returns False.

EXAMPLES::

sage: import sage.combinat.partition_algebra as pa

sage: pa.is_planar( pa.to_set_partition([[1,-2],[2,-1]]))

False

sage: pa.is_planar( pa.to_set_partition([[1,-1],[2,-2]]))

True

"""

#Singletons don't affect planarity

to_consider = [x for x in map(list, sp) if len(x) > 1]

n = len(to_consider)

for i in range(n):

#Get the positive and negative entries of this

#part

ap = [x for x in to_consider[i] if x>0]

an = [abs(x) for x in to_consider[i] if x<0]

#print a, ap, an

#Check if a includes numbers in both the top and bottom rows

if len(ap) > 0 and len(an) > 0:

for j in range(n):

if i == j:

continue

#Get the positive and negative entries of this part

bp = [x for x in to_consider[j] if x>0]

bn = [abs(x) for x in to_consider[j] if x<0]

#Skip the ones that don't involve numbers in both

#the bottom and top rows

if len(bn) == 0 or len(bp) == 0:

continue

#Make sure that if min(bp) > max(ap)

#then min(bn) > max(an)

if max(bp) > max(ap):

if min(bn) < min(an):

return False

#Go through the bottom and top rows

for row in [ap, an]:

if len(row) > 1:

row.sort()

for s in range(len(row)-1):

if row[s] + 1 == row[s+1]:

#No gap, continue on

continue

else:

rng = list(range(row[s] + 1, row[s + 1]))

#Go through and make sure any parts that

#contain numbers in this range are completely

#contained in this range

for j in range(n):

if i == j:

continue

#Make sure we make the numbers negative again

#if we are in the bottom row

if row is ap:

sr = Set(rng)

else:

sr = Set([-1*x for x in rng])

sj = Set(to_consider[j])

intersection = sr.intersection(sj)

if intersection:

if sj != intersection:

return False

return True

def to_graph(sp):

"""

Returns a graph representing the set partition sp.

EXAMPLES::

sage: import sage.combinat.partition_algebra as pa

sage: g = pa.to_graph( pa.to_set_partition([[1,-2],[2,-1]])); g

Graph on 4 vertices

sage: g.vertices() #random

[1, 2, -2, -1]

sage: g.edges() #random

[(1, -2, None), (2, -1, None)]

"""

g = Graph()

for part in sp:

part_list = list(part)

if len(part_list) > 0:

g.add_vertex(part_list[0])

for i in range(1, len(part_list)):

g.add_vertex(part_list[i])

g.add_edge(part_list[i-1], part_list[i])

return g

def pair_to_graph(sp1, sp2):

"""

Return a graph consisting of the disjoint union of the graphs of set

partitions ``sp1`` and ``sp2`` along with edges joining the bottom

row (negative numbers) of ``sp1`` to the top row (positive numbers)

of ``sp2``.

The vertices of the graph ``sp1`` appear in the result as pairs

``(k, 1)``, whereas the vertices of the graph ``sp2`` appear as

pairs ``(k, 2)``.

EXAMPLES::

sage: import sage.combinat.partition_algebra as pa

sage: sp1 = pa.to_set_partition([[1,-2],[2,-1]])

sage: sp2 = pa.to_set_partition([[1,-2],[2,-1]])

sage: g = pa.pair_to_graph( sp1, sp2 ); g

Graph on 8 vertices

sage: g.vertices() #random

[(1, 2), (-1, 1), (-2, 2), (-1, 2), (-2, 1), (2, 1), (2, 2), (1, 1)]

sage: g.edges() #random

[((1, 2), (-1, 1), None),

((1, 2), (-2, 2), None),

((-1, 1), (2, 1), None),

((-1, 2), (2, 2), None),

((-2, 1), (1, 1), None),

((-2, 1), (2, 2), None)]

Another example which used to be wrong until :trac:`15958`::

sage: sp3 = pa.to_set_partition([[1, -1], [2], [-2]])

sage: sp4 = pa.to_set_partition([[1], [-1], [2], [-2]])

sage: g = pa.pair_to_graph( sp3, sp4 ); g

Graph on 8 vertices

sage: g.vertices()

[(-2, 1), (-2, 2), (-1, 1), (-1, 2), (1, 1), (1, 2), (2, 1), (2, 2)]

sage: g.edges()

[((-2, 1), (2, 2), None), ((-1, 1), (1, 1), None),

((-1, 1), (1, 2), None)]

"""

g = Graph()

#Add the first set partition to the graph

for part in sp1:

part_list = list(part)

if len(part_list) > 0:

g.add_vertex( (part_list[0],1) )

#Add the edge to the second part of the graph

if part_list[0] < 0:

g.add_edge( (part_list[0], 1), (abs(part_list[0]), 2) )

for i in range(1, len(part_list)):

g.add_vertex( (part_list[i], 1) )

#Add the edge to the second part of the graph

if part_list[i] < 0:

g.add_edge( (part_list[i], 1), (abs(part_list[i]), 2) )

#Add the edge between adjacent elements of a part

g.add_edge( (part_list[i-1], 1), (part_list[i], 1) )

#Add the second set partition to the graph

for part in sp2:

part_list = list(part)

if len(part_list) > 0:

g.add_vertex( (part_list[0], 2) )

for i in range(1, len(part_list)):

g.add_vertex( (part_list[i], 2) )

g.add_edge( (part_list[i-1], 2), (part_list[i], 2) )

return g

def propagating_number(sp):

"""

Returns the propagating number of the set partition sp. The

propagating number is the number of blocks with both a positive and

negative number.

EXAMPLES::

sage: import sage.combinat.partition_algebra as pa

sage: sp1 = pa.to_set_partition([[1,-2],[2,-1]])

sage: sp2 = pa.to_set_partition([[1,2],[-2,-1]])

sage: pa.propagating_number(sp1)

sage: pa.propagating_number(sp2)

"""

pn = 0

for part in sp:

if min(part) < 0 and max(part) > 0:

pn += 1

return pn

def to_set_partition(l,k=None):

"""

Coverts a list of a list of numbers to a set partitions. Each list

of numbers in the outer list specifies the numbers contained in one

of the blocks in the set partition.

If k is specified, then the set partition will be a set partition

of 1, ..., k, -1, ..., -k. Otherwise, k will default to the minimum

number needed to contain all of the specified numbers.

EXAMPLES::

sage: import sage.combinat.partition_algebra as pa

sage: pa.to_set_partition([[1,-1],[2,-2]]) == pa.identity(2)

True

"""

if k is None:

if l == []:

return Set([])

else:

k = max( (max( map(abs, x) ) for x in l) )

to_be_added = Set( list(range(1, k+1)) + [-1*x for x in range(1, k+1)] )

sp = []

for part in l:

spart = Set(part)

to_be_added -= spart

sp.append(spart)

for singleton in to_be_added:

sp.append(Set([singleton]))

return Set(sp)

def identity(k):

"""

Returns the identity set partition 1, -1, ..., k, -k

EXAMPLES::

sage: import sage.combinat.partition_algebra as pa

sage: pa.identity(2)

{{2, -2}, {1, -1}}

"""

res = []

for i in range(1, k+1):

res.append(Set([i, -i]))

return Set(res)

def set_partition_composition(sp1, sp2):

"""

Returns a tuple consisting of the composition of the set partitions

sp1 and sp2 and the number of components removed from the middle

rows of the graph.

EXAMPLES::

sage: import sage.combinat.partition_algebra as pa

sage: sp1 = pa.to_set_partition([[1,-2],[2,-1]])

sage: sp2 = pa.to_set_partition([[1,-2],[2,-1]])

sage: pa.set_partition_composition(sp1, sp2) == (pa.identity(2), 0)

True

"""

g = pair_to_graph(sp1, sp2)

connected_components = g.connected_components()

res = []

total_removed = 0

for cc in connected_components:

#Remove the vertices that live in the middle two rows

new_cc = [x for x in cc if not( (x[0]<0 and x[1] == 1) or (x[0]>0 and x[1]==2) )]

if new_cc == []:

if len(cc) > 1:

total_removed += 1

else:

res.append( Set([x[0] for x in new_cc]) )

return ( Set(res), total_removed )

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

554 statements 398 run 156 missing 0 excluded