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

sage: spin_rec(t, [[t^5], [t^4], [t^6 + t^4 + t^2]], [[[2, 2, 2, 2, 1], [0, 0, 3]], [[3, 3, 1, 1, 1], [0, 3, 0]], [[3, 3, 3], [3, 0, 0]]], sp([[3, 3, 3, 2, 1], []]), [2, 1, 1], 3)

[2*t^7 + 2*t^5 + t^3]

"""

if not current:

return [parent(t).zero()]

tmp = []

partp = part[0].conjugate()

ell = len(partp)

#compute the contribution of the ribbons added at

#the current node

for val in current:

perms = val[1]

perm = [partp[i] + ell - (i + 1) - perms[i] for i in reversed(range(ell))]

perm = to_standard(perm)

tmp.append( weight[-1]*(length-1) - perm.number_of_inversions() )

if nexts:

return [ sum(sum(t**tval * nval for nval in nexts[i])

for i, tval in enumerate(tmp)) ]

else:

return [ sum(t**val for val in tmp) ]

def spin_polynomial_square(part, weight, length):

r"""

Returns the spin polynomial associated with ``part``, ``weight``, and

``length``, with the substitution `t \to t^2` made.

EXAMPLES::

sage: from sage.combinat.ribbon_tableau import spin_polynomial_square

sage: spin_polynomial_square([6,6,6],[4,2],3)

t^12 + t^10 + 2*t^8 + t^6 + t^4

sage: spin_polynomial_square([6,6,6],[4,1,1],3)

t^12 + 2*t^10 + 3*t^8 + 2*t^6 + t^4

sage: spin_polynomial_square([3,3,3,2,1], [2,2], 3)

t^7 + t^5

sage: spin_polynomial_square([3,3,3,2,1], [2,1,1], 3)

2*t^7 + 2*t^5 + t^3

sage: spin_polynomial_square([3,3,3,2,1], [1,1,1,1], 3)

3*t^7 + 5*t^5 + 3*t^3 + t

sage: spin_polynomial_square([5,4,3,2,1,1,1], [2,2,1], 3)

2*t^9 + 6*t^7 + 2*t^5

sage: spin_polynomial_square([[6]*6, [3,3]], [4,4,2], 3)

3*t^18 + 5*t^16 + 9*t^14 + 6*t^12 + 3*t^10

"""

R = ZZ['t']

if part in _Partitions:

part = SkewPartition([part,_Partitions([])])

elif part in SkewPartitions():

part = SkewPartition(part)

if part == [[],[]] and weight == []:

return R.one()

t = R.gen()

return R(graph_implementation_rec(part, weight, length, functools.partial(spin_rec,t))[0])

def spin_polynomial(part, weight, length):

"""

Returns the spin polynomial associated to ``part``, ``weight``, and

``length``.

EXAMPLES::

sage: from sage.combinat.ribbon_tableau import spin_polynomial

sage: spin_polynomial([6,6,6],[4,2],3)

t^6 + t^5 + 2*t^4 + t^3 + t^2

sage: spin_polynomial([6,6,6],[4,1,1],3)

t^6 + 2*t^5 + 3*t^4 + 2*t^3 + t^2

sage: spin_polynomial([3,3,3,2,1], [2,2], 3)

t^(7/2) + t^(5/2)

sage: spin_polynomial([3,3,3,2,1], [2,1,1], 3)

2*t^(7/2) + 2*t^(5/2) + t^(3/2)

sage: spin_polynomial([3,3,3,2,1], [1,1,1,1], 3)

3*t^(7/2) + 5*t^(5/2) + 3*t^(3/2) + sqrt(t)

sage: spin_polynomial([5,4,3,2,1,1,1], [2,2,1], 3)

2*t^(9/2) + 6*t^(7/2) + 2*t^(5/2)

sage: spin_polynomial([[6]*6, [3,3]], [4,4,2], 3)

3*t^9 + 5*t^8 + 9*t^7 + 6*t^6 + 3*t^5

"""

from sage.symbolic.ring import SR

sp = spin_polynomial_square(part, weight, length)

t = SR.var('t')

coeffs = sp.list()

return sum(c * t**(QQ(i)/2) for i,c in enumerate(coeffs))

def cospin_polynomial(part, weight, length):

"""

Return the cospin polynomial associated to ``part``, ``weight``, and

``length``.

EXAMPLES::

sage: from sage.combinat.ribbon_tableau import cospin_polynomial

sage: cospin_polynomial([6,6,6],[4,2],3)

t^4 + t^3 + 2*t^2 + t + 1

sage: cospin_polynomial([3,3,3,2,1], [3,1], 3)

sage: cospin_polynomial([3,3,3,2,1], [2,2], 3)

t + 1

sage: cospin_polynomial([3,3,3,2,1], [2,1,1], 3)

t^2 + 2*t + 2

sage: cospin_polynomial([3,3,3,2,1], [1,1,1,1], 3)

t^3 + 3*t^2 + 5*t + 3

sage: cospin_polynomial([5,4,3,2,1,1,1], [2,2,1], 3)

2*t^2 + 6*t + 2

sage: cospin_polynomial([[6]*6, [3,3]], [4,4,2], 3)

3*t^4 + 6*t^3 + 9*t^2 + 5*t + 3

"""

R = ZZ['t']

# The power in the spin polynomial are all half integers

# or all integers. Manipulation of expressions need to

# separate cases

sp = spin_polynomial_square(part, weight, length)

if sp == 0:

return R.zero()

coeffs = [c for c in sp.list() if c != 0]

d = len(coeffs) - 1

t = R.gen()

return R( sum(c * t**(d-i) for i,c in enumerate(coeffs)) )

## //////////////////////////////////////////////////////////////////////////////////////////

## // Generic function for driving into the graph of partitions coding all ribbons

## // tableaux of a given shape and weight

## //////////////////////////////////////////////////////////////////////////////////////////

## //This function construct the graph of the set of k-ribbon tableaux

## //of a given skew shape and a given weight.

## //The first argument is always a skew partition.

## //In the case where the inner partition is empty there is no branch without solutions

## //In the other cases there is in average a lot of branches without solutions

## /////////////////////////////////////////////////////////////////////////////////////////

def graph_implementation_rec(skp, weight, length, function):

"""

TESTS::

sage: from sage.combinat.ribbon_tableau import graph_implementation_rec, list_rec

sage: graph_implementation_rec(SkewPartition([[1], []]), [1], 1, list_rec)

[[[], [[1]]]]

sage: graph_implementation_rec(SkewPartition([[2, 1], []]), [1, 2], 1, list_rec)

[[[], [[2], [1, 2]]]]

sage: graph_implementation_rec(SkewPartition([[], []]), [0], 1, list_rec)

[[[], []]]

"""

if sum(weight) == 0:

weight = []

partp = skp[0].conjugate()

ell = len(partp)

outer = skp[1]

outer_len = len(outer)

## Some tests in order to know if the shape and the weight are compatible.

if weight != [] and weight[-1] <= len(partp):

perms = permutation.Permutations([0]*(len(partp)-weight[-1]) + [length]*(weight[-1])).list()

else:

return function([], [], skp, weight, length)

selection = []

for j in range(len(perms)):

retire = [(val + ell - (i+1) - perms[j][i]) for i,val in enumerate(partp)]

retire.sort(reverse=True)

retire = [val - ell + (i+1) for i,val in enumerate(retire)]

if retire[-1] >= 0 and retire == sorted(retire, reverse=True):

retire = Partition(retire).conjugate()

# Cutting branches if the retired partition has a line strictly included into the inner one

if len(retire) >= outer_len:

append = True

for k in range(outer_len):

if retire[k] - outer[k] < 0:

append = False

break

if append:

selection.append([retire, perms[j]])

#selection contains the list of current nodes

if len(weight) == 1:

return function([], selection, skp, weight, length)

else:

#The recursive calls permit us to construct the list of the sons

#of all current nodes in selection

a = [graph_implementation_rec([p[0], outer], weight[:-1], length, function)

for p in selection]

return function(a, selection, skp, weight, length)

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

class MultiSkewTableau(CombinatorialElement):

"""

A multi skew tableau which is a tuple of skew tableaux.

EXAMPLES::

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

sage: s.size()

sage: s.weight()

[2, 3, 1]

sage: s.shape()

[[2, 2] / [1], [2, 1] / []]

TESTS::

sage: mst = MultiSkewTableau([ [[None,1],[2,3]], [[1,2],[2]] ])

sage: TestSuite(mst).run()

"""

@staticmethod

def __classcall_private__(cls, x):

"""

Construct a multi skew tableau.

EXAMPLES::

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

"""

if isinstance(x, MultiSkewTableau):

return x

return MultiSkewTableaux()([SkewTableau(i) for i in x] )

def size(self):

"""

Return the size of ``self``, which is the sum of the sizes of the skew

tableaux in ``self``.

EXAMPLES::

sage: s = SemistandardSkewTableaux([[2,2],[1]]).list()

sage: a = MultiSkewTableau([s[0],s[1],s[2]])

sage: a.size()

"""

return sum(x.size() for x in self)

def weight(self):

"""

Return the weight of ``self``.

EXAMPLES::

sage: s = SemistandardSkewTableaux([[2,2],[1]]).list()

sage: a = MultiSkewTableau([s[0],s[1],s[2]])

sage: a.weight()

[5, 3, 1]

"""

weights = [x.weight() for x in self]

m = max([len(x) for x in weights])

weight = [0]*m

for w in weights:

for i in range(len(w)):

weight[i] += w[i]

return weight

def shape(self):

"""

Return the shape of ``self``.

EXAMPLES::

sage: s = SemistandardSkewTableaux([[2,2],[1]]).list()

sage: a = MultiSkewTableau([s[0],s[1],s[2]])

sage: a.shape()

[[2, 2] / [1], [2, 2] / [1], [2, 2] / [1]]

"""

return [x.shape() for x in self]

def inversion_pairs(self):

"""

Return a list of the inversion pairs of ``self``.

EXAMPLES::

sage: s = MultiSkewTableau([ [[2,3],[5,5]], [[1,1],[3,3]], [[2],[6]] ])

sage: s.inversion_pairs()

[((0, (0, 0)), (1, (0, 0))),

((0, (1, 0)), (1, (0, 1))),

((0, (1, 1)), (1, (0, 0))),

((0, (1, 1)), (1, (1, 1))),

((0, (1, 1)), (2, (0, 0))),

((1, (0, 1)), (2, (0, 0))),

((1, (1, 1)), (2, (0, 0)))]

"""

inv = []

for k in range(len(self)):

for b in self[k].cells():

inv += self._inversion_pairs_from_position(k,b)

return inv

def inversions(self):

"""

Return the number of inversion pairs of ``self``.

EXAMPLES::

sage: t1 = SkewTableau([[1]])

sage: t2 = SkewTableau([[2]])

sage: MultiSkewTableau([t1,t1]).inversions()

sage: MultiSkewTableau([t1,t2]).inversions()

sage: MultiSkewTableau([t2,t2]).inversions()

sage: MultiSkewTableau([t2,t1]).inversions()

sage: s = MultiSkewTableau([ [[2,3],[5,5]], [[1,1],[3,3]], [[2],[6]] ])

sage: s.inversions()

"""

return len(self.inversion_pairs())

def _inversion_pairs_from_position(self, k, ij):

"""

Return the number of inversions at the cell position `(i,j)` in the

``k``-th tableaux in ``self``.

EXAMPLES::

sage: s = MultiSkewTableau([ [[2,3],[5,5]], [[1,1],[3,3]], [[2],[6]] ])

sage: s._inversion_pairs_from_position(0, (1,1))

[((0, (1, 1)), (1, (0, 0))),

((0, (1, 1)), (1, (1, 1))),

((0, (1, 1)), (2, (0, 0)))]

sage: s._inversion_pairs_from_position(1, (0,1))

[((1, (0, 1)), (2, (0, 0)))]

"""

pk = k

pi,pj = ij

c = pi - pj

value = self[pk][pi][pj]

pk_cells = self[pk].cells_by_content(c)

same_diagonal = [ t.cells_by_content(c) for t in self[pk+1:] ]

above_diagonal = [ t.cells_by_content(c+1) for t in self[pk+1:] ]

res = []

for i,j in pk_cells:

if pi < i and value > self[pk][i][j]:

res.append( ((pk,(pi,pj)), (pk,(i,j))) )

for k in range(len(same_diagonal)):

for i,j in same_diagonal[k]:

if value > self[pk+k+1][i][j]:

res.append( ((pk,(pi,pj)), (pk+k+1,(i,j))) )

for k in range(len(above_diagonal)):

for i,j in above_diagonal[k]:

if value < self[pk+k+1][i][j]:

res.append( ((pk,(pi,pj)), (pk+k+1,(i,j))) )

return res

class MultiSkewTableaux(UniqueRepresentation, Parent):

r"""

Multiskew tableaux.

"""

def __init__(self, category=None):

"""

EXAMPLES::

sage: R = MultiSkewTableaux()

sage: TestSuite(R).run()

"""

if category is None:

category = Sets()

Parent.__init__(self, category=category)

def _repr_(self):

"""

Return a string representation of ``self``.

EXAMPLES::

sage: MultiSkewTableaux()

Multi Skew Tableaux tableaux

"""

return "Multi Skew Tableaux tableaux"

def _element_constructor_(self, rt):

"""

Construct an element of ``self`` from ``rt``.

EXAMPLES::

sage: R = MultiSkewTableaux()

sage: R([[[1, 1], [2]], [[None, 2], [3, 3]]])

[[[1, 1], [2]], [[None, 2], [3, 3]]]

"""

return self.element_class(self, rt)

Element = MultiSkewTableau

class SemistandardMultiSkewTableaux(MultiSkewTableaux):

"""

Semistandard multi skew tableaux.

A multi skew tableau is a `k`-tuple of skew tableaux of

given shape with a specified total weight.

EXAMPLES::

sage: S = SemistandardMultiSkewTableaux([ [[2,1],[]], [[2,2],[1]] ], [2,2,2]); S

Semistandard multi skew tableaux of shape [[2, 1] / [], [2, 2] / [1]] and weight [2, 2, 2]

sage: S.list()

[[[[1, 1], [2]], [[None, 2], [3, 3]]],

[[[1, 2], [2]], [[None, 1], [3, 3]]],

[[[1, 3], [2]], [[None, 2], [1, 3]]],

[[[1, 3], [2]], [[None, 1], [2, 3]]],

[[[1, 1], [3]], [[None, 2], [2, 3]]],

[[[1, 2], [3]], [[None, 2], [1, 3]]],

[[[1, 2], [3]], [[None, 1], [2, 3]]],

[[[2, 2], [3]], [[None, 1], [1, 3]]],

[[[1, 3], [3]], [[None, 1], [2, 2]]],

[[[2, 3], [3]], [[None, 1], [1, 2]]]]

"""

@staticmethod

def __classcall_private__(cls, shape, weight):

"""

Normalize input to ensure a unique representation.

EXAMPLES::

sage: S1 = SemistandardMultiSkewTableaux([ [[2,1],[]], [[2,2],[1]] ], [2,2,2])

sage: shape_alt = ( SkewPartition([[2,1],[]]), SkewPartition([[2,2],[1]]) )

sage: S2 = SemistandardMultiSkewTableaux(shape_alt, (2,2,2))

sage: S1 is S2

True

"""

shape = tuple(SkewPartition(x) for x in shape)

weight = Partition(weight)

if sum(weight) != sum(s.size() for s in shape):

raise ValueError("the sum of weight must be the sum of the sizes of shape")

return super(SemistandardMultiSkewTableaux, cls).__classcall__(cls, shape, weight)

def __init__(self, shape, weight):

"""

TESTS::

sage: S = SemistandardMultiSkewTableaux([ [[2,1],[]], [[2,2],[1]] ], [2,2,2])

sage: TestSuite(S).run()

"""

self._shape = shape

self._weight = weight

MultiSkewTableaux.__init__(self, category=FiniteEnumeratedSets())

def _repr_(self):

"""

Return a string representation of ``self``.

EXAMPLES::

sage: SemistandardMultiSkewTableaux([ [[2,1],[]], [[2,2],[1]] ], [2,2,2])

Semistandard multi skew tableaux of shape [[2, 1] / [], [2, 2] / [1]] and weight [2, 2, 2]

"""

return "Semistandard multi skew tableaux of shape %s and weight %s"%(list(self._shape), self._weight)

def __contains__(self, x):

"""

TESTS::

sage: s = SemistandardMultiSkewTableaux([ [[2,1],[]], [[2,2],[1]] ], [2,2,2])

sage: all(i in s for i in s)

True

"""

try:

x = MultiSkewTableau(x)

except TypeError:

return False

if x.weight() != list(self._weight):

return False

if x.shape() != list(self._shape):

return False

if not all( x[i].is_semistandard() for i in range(len(x)) ):

return False

return True

def __iter__(self):

"""

EXAMPLES::

sage: sp = SkewPartitions(3).list()

sage: SemistandardMultiSkewTableaux([SkewPartition([[1, 1, 1], []]), SkewPartition([[3], []])],[2,2,2]).list()

[[[[1], [2], [3]], [[1, 2, 3]]]]

sage: a = SkewPartition([[8,7,6,5,1,1],[2,1,1]])

sage: weight = [3,3,2]

sage: k = 3

sage: s = SemistandardMultiSkewTableaux(a.quotient(k),weight)

sage: len(s.list())

sage: RibbonTableaux(a,weight,k).cardinality()

"""

parts = self._shape

mu = self._weight

#Splitting the partition

s = [ p.size() for p in parts ]

parts = [p.to_list() for p in parts]

#Gluing the partitions

parttmp = parts[0]

i = 1

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

trans = parttmp[0][0]

current_part = parts[i]

current_part[1] += [0]*(len(current_part[0])-len(current_part[1]))

inner_current = [ trans + j for j in current_part[1] ]

outer_current = [ trans + j for j in current_part[0] ]

parttmp = [ outer_current + parttmp[0], inner_current + parttmp[1] ]

#List the corresponding skew tableaux

l = [ st.to_word() for st in SemistandardSkewTableaux(parttmp, mu) ]

S = SkewTableaux()

for k in range(len(l)):

pos = 0 #Double check this

restmp = [ S.from_shape_and_word(parts[0], [l[k][j] for j in range(s[0])]) ]

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

w = [l[k][j] for j in range(pos+s[i-1], pos+s[i-1]+s[i])]

restmp.append( S.from_shape_and_word(parts[i], w) )

yield self.element_class(self, restmp)

class RibbonTableau_class(RibbonTableau):

"""

This exists solely for unpickling ``RibbonTableau_class`` objects.

"""

def __setstate__(self, state):

r"""

Unpickle old ``RibbonTableau_class`` objects.

TESTS::

sage: loads(b'x\x9c5\xcc\xbd\x0e\xc2 \x14@\xe1\xb4Z\x7f\xd0\x07\xc1\x85D}\x8f\x0e\x8d\x1d\t\xb9\x90\x1bJ\xa44\x17\xe8h\xa2\x83\xef-\xda\xb8\x9do9\xcf\xda$\xb0(\xcc4j\x17 \x8b\xe8\xb4\x9e\x82\xca\xa0=\xc2\xcc\xba\x1fo\x8b\x94\xf1\x90\x12\xa3\xea\xf4\xa2\xfaA+\xde7j\x804\xd0\xba-\xe5]\xca\xd4H\xdapI[\xde.\xdf\xe8\x82M\xc2\x85\x8c\x16#\x1b\xe1\x8e\xea\x0f\xda\xf5\xd5\xf9\xdd\xd1\x1e%1>\x14]\x8a\x0e\xdf\xb8\x968"\xceZ|\x00x\xef5\x11')

[[None, 1], [2, 3]]

sage: loads(dumps( RibbonTableau([[None, 1],[2,3]]) ))

[[None, 1], [2, 3]]

"""

self.__class__ = RibbonTableau

self.__init__(RibbonTableaux(), state['_list'])

from sage.structure.sage_object import register_unpickle_override

register_unpickle_override('sage.combinat.ribbon_tableau', 'RibbonTableau_class', RibbonTableau_class)

register_unpickle_override('sage.combinat.ribbon_tableau', 'RibbonTableaux_shapeweightlength', RibbonTableaux)

register_unpickle_override('sage.combinat.ribbon_tableau', 'SemistandardMultiSkewTtableaux_shapeweight', SemistandardMultiSkewTableaux)

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

310 statements 221 run 89 missing 0 excluded