Combinatorial maps#

This module provides a decorator that can be used to add semantic to a Python method by marking it as implementing a combinatorial map, that is a map between two enumerated sets:

sage: from sage.combinat.combinatorial_map import combinatorial_map
sage: class MyPermutation():
....:     @combinatorial_map()
....:     def reverse(self):
....:         '''
....:         Reverse the permutation
....:         '''
....:         # ... code ...

>>> from sage.all import *
>>> from sage.combinat.combinatorial_map import combinatorial_map
>>> class MyPermutation():
...     @combinatorial_map()
...     def reverse(self):
...         '''
...         Reverse the permutation
...         '''
...         # ... code ...

By default, this decorator is a no-op: it returns the decorated method as is:

sage: MyPermutation.reverse
<function MyPermutation.reverse at ...>

>>> from sage.all import *
>>> MyPermutation.reverse
<function MyPermutation.reverse at ...>

See combinatorial_map_wrapper() for the various options this decorator can take.

Projects built on top of Sage are welcome to customize locally this hook to instrument the Sage code and exploit this semantic information. Typically, the decorator could be used to populate a database of maps. For a real-life application, see the project \(FindStat <http://findstat.org/>\). As a basic example, a variant of the decorator is provided as combinatorial_map_wrapper(); it wraps the decorated method, so that one can later use combinatorial_maps_in_class() to query an object, or class thereof, for all the combinatorial maps that apply to it.

Note

Since decorators are evaluated upon loading Python modules, customizing combinatorial map needs to be done before the modules using it are loaded. In the examples below, where we illustrate the customized combinatorial_map decorator on the sage.combinat.permutation module, we resort to force a reload of this module after dynamically changing sage.combinat.combinatorial_map.combinatorial_map. This is good enough for those doctests, but remains fragile.

For real use cases, it is probably best to just edit this source file statically (see below).

class sage.combinat.combinatorial_map.CombinatorialMap(f, order=None, name=None)[source]#

Bases: object

This is a wrapper class for methods that are combinatorial maps.

For further details and doctests, see Combinatorial maps and combinatorial_map_wrapper().

name()[source]#

Returns the name of a combinatorial map. This is used for the string representation of self.

EXAMPLES:

sage: from sage.combinat.combinatorial_map import combinatorial_map
sage: class CombinatorialClass:
....:     @combinatorial_map(name='map1')
....:     def to_self_1(): pass
....:     @combinatorial_map()
....:     def to_self_2(): pass
sage: CombinatorialClass.to_self_1.name()
'map1'
sage: CombinatorialClass.to_self_2.name()
'to_self_2'

>>> from sage.all import *
>>> from sage.combinat.combinatorial_map import combinatorial_map
>>> class CombinatorialClass:
...     @combinatorial_map(name='map1')
...     def to_self_1(): pass
...     @combinatorial_map()
...     def to_self_2(): pass
>>> CombinatorialClass.to_self_1.name()
'map1'
>>> CombinatorialClass.to_self_2.name()
'to_self_2'
order()[source]#

Returns the order of self, or None if the order is not known.

EXAMPLES:

sage: from sage.combinat.combinatorial_map import combinatorial_map
sage: class CombinatorialClass:
....:     @combinatorial_map(order=2)
....:     def to_self_1(): pass
....:     @combinatorial_map()
....:     def to_self_2(): pass
sage: CombinatorialClass.to_self_1.order()
2
sage: CombinatorialClass.to_self_2.order() is None
True

>>> from sage.all import *
>>> from sage.combinat.combinatorial_map import combinatorial_map
>>> class CombinatorialClass:
...     @combinatorial_map(order=Integer(2))
...     def to_self_1(): pass
...     @combinatorial_map()
...     def to_self_2(): pass
>>> CombinatorialClass.to_self_1.order()
2
>>> CombinatorialClass.to_self_2.order() is None
True
unbounded_map()[source]#

Return the unbounded version of self.

You can use this method to return a function which takes as input an element in the domain of the combinatorial map. See the example below.

EXAMPLES:

sage: sage.combinat.combinatorial_map.combinatorial_map = sage.combinat.combinatorial_map.combinatorial_map_wrapper
sage: from importlib import reload
sage: _ = reload(sage.combinat.permutation)
sage: from sage.combinat.permutation import Permutation
sage: pi = Permutation([1,3,2])
sage: f = pi.reverse
sage: F = f.unbounded_map()
sage: F(pi)
[2, 3, 1]

>>> from sage.all import *
>>> sage.combinat.combinatorial_map.combinatorial_map = sage.combinat.combinatorial_map.combinatorial_map_wrapper
>>> from importlib import reload
>>> _ = reload(sage.combinat.permutation)
>>> from sage.combinat.permutation import Permutation
>>> pi = Permutation([Integer(1),Integer(3),Integer(2)])
>>> f = pi.reverse
>>> F = f.unbounded_map()
>>> F(pi)
[2, 3, 1]
sage.combinat.combinatorial_map.combinatorial_map(f=None, order=None, name=None)[source]#

Combinatorial map decorator

See Combinatorial maps for a description of this decorator and its purpose. This default implementation does nothing.

INPUT:

  • f – (default: None, if combinatorial_map is used as a decorator) a function

  • name – (default: None) the name for nicer outputs on combinatorial maps

  • order – (default: None) the order of the combinatorial map, if it is known. Is not used, but might be helpful later

OUTPUT:

  • f unchanged

EXAMPLES:

sage: from sage.combinat.combinatorial_map import combinatorial_map_trivial as combinatorial_map
sage: class MyPermutation():
....:     @combinatorial_map
....:     def reverse(self):
....:         '''
....:         Reverse the permutation
....:         '''
....:         # ... code ...
....:     @combinatorial_map(name='descent set of permutation')
....:     def descent_set(self):
....:         '''
....:         The descent set of the permutation
....:         '''
....:         # ... code ...

sage: MyPermutation.reverse
<function MyPermutation.reverse at ...>

sage: MyPermutation.descent_set
<function MyPermutation.descent_set at ...>

>>> from sage.all import *
>>> from sage.combinat.combinatorial_map import combinatorial_map_trivial as combinatorial_map
>>> class MyPermutation():
...     @combinatorial_map
...     def reverse(self):
...         '''
...         Reverse the permutation
...         '''
...         # ... code ...
...     @combinatorial_map(name='descent set of permutation')
...     def descent_set(self):
...         '''
...         The descent set of the permutation
...         '''
...         # ... code ...

>>> MyPermutation.reverse
<function MyPermutation.reverse at ...>

>>> MyPermutation.descent_set
<function MyPermutation.descent_set at ...>
sage.combinat.combinatorial_map.combinatorial_map_trivial(f=None, order=None, name=None)[source]#

Combinatorial map decorator

See Combinatorial maps for a description of this decorator and its purpose. This default implementation does nothing.

INPUT:

  • f – (default: None, if combinatorial_map is used as a decorator) a function

  • name – (default: None) the name for nicer outputs on combinatorial maps

  • order – (default: None) the order of the combinatorial map, if it is known. Is not used, but might be helpful later

OUTPUT:

  • f unchanged

EXAMPLES:

sage: from sage.combinat.combinatorial_map import combinatorial_map_trivial as combinatorial_map
sage: class MyPermutation():
....:     @combinatorial_map
....:     def reverse(self):
....:         '''
....:         Reverse the permutation
....:         '''
....:         # ... code ...
....:     @combinatorial_map(name='descent set of permutation')
....:     def descent_set(self):
....:         '''
....:         The descent set of the permutation
....:         '''
....:         # ... code ...

sage: MyPermutation.reverse
<function MyPermutation.reverse at ...>

sage: MyPermutation.descent_set
<function MyPermutation.descent_set at ...>

>>> from sage.all import *
>>> from sage.combinat.combinatorial_map import combinatorial_map_trivial as combinatorial_map
>>> class MyPermutation():
...     @combinatorial_map
...     def reverse(self):
...         '''
...         Reverse the permutation
...         '''
...         # ... code ...
...     @combinatorial_map(name='descent set of permutation')
...     def descent_set(self):
...         '''
...         The descent set of the permutation
...         '''
...         # ... code ...

>>> MyPermutation.reverse
<function MyPermutation.reverse at ...>

>>> MyPermutation.descent_set
<function MyPermutation.descent_set at ...>
sage.combinat.combinatorial_map.combinatorial_map_wrapper(f=None, order=None, name=None)[source]#

Combinatorial map decorator (basic example).

See Combinatorial maps for a description of the combinatorial_map decorator and its purpose. This implementation, together with combinatorial_maps_in_class() illustrates how to use this decorator as a hook to instrument the Sage code.

INPUT:

  • f – (default: None, if combinatorial_map is used as a decorator) a function

  • name – (default: None) the name for nicer outputs on combinatorial maps

  • order – (default: None) the order of the combinatorial map, if it is known. Is not used, but might be helpful later

OUTPUT:

EXAMPLES:

We define a class illustrating the use of this implementation of the combinatorial_map decorator with its various arguments:

sage: from sage.combinat.combinatorial_map import combinatorial_map_wrapper as combinatorial_map
sage: class MyPermutation():
....:     @combinatorial_map()
....:     def reverse(self):
....:         '''
....:         Reverse the permutation
....:         '''
....:         pass
....:     @combinatorial_map(order=2)
....:     def inverse(self):
....:         '''
....:         The inverse of the permutation
....:         '''
....:         pass
....:     @combinatorial_map(name='descent set of permutation')
....:     def descent_set(self):
....:         '''
....:         The descent set of the permutation
....:         '''
....:         pass
....:     def major_index(self):
....:         '''
....:         The major index of the permutation
....:         '''
....:         pass
sage: MyPermutation.reverse
Combinatorial map: reverse
sage: MyPermutation.descent_set
Combinatorial map: descent set of permutation
sage: MyPermutation.inverse
Combinatorial map: inverse

>>> from sage.all import *
>>> from sage.combinat.combinatorial_map import combinatorial_map_wrapper as combinatorial_map
>>> class MyPermutation():
...     @combinatorial_map()
...     def reverse(self):
...         '''
...         Reverse the permutation
...         '''
...         pass
...     @combinatorial_map(order=Integer(2))
...     def inverse(self):
...         '''
...         The inverse of the permutation
...         '''
...         pass
...     @combinatorial_map(name='descent set of permutation')
...     def descent_set(self):
...         '''
...         The descent set of the permutation
...         '''
...         pass
...     def major_index(self):
...         '''
...         The major index of the permutation
...         '''
...         pass
>>> MyPermutation.reverse
Combinatorial map: reverse
>>> MyPermutation.descent_set
Combinatorial map: descent set of permutation
>>> MyPermutation.inverse
Combinatorial map: inverse

One can now determine all the combinatorial maps associated with a given object as follows:

sage: from sage.combinat.combinatorial_map import combinatorial_maps_in_class
sage: X = combinatorial_maps_in_class(MyPermutation); X # random
[Combinatorial map: reverse,
 Combinatorial map: descent set of permutation,
 Combinatorial map: inverse]

>>> from sage.all import *
>>> from sage.combinat.combinatorial_map import combinatorial_maps_in_class
>>> X = combinatorial_maps_in_class(MyPermutation); X # random
[Combinatorial map: reverse,
 Combinatorial map: descent set of permutation,
 Combinatorial map: inverse]

The method major_index defined about is not a combinatorial map:

sage: MyPermutation.major_index
<function MyPermutation.major_index at ...>

>>> from sage.all import *
>>> MyPermutation.major_index
<function MyPermutation.major_index at ...>

But one can define a function that turns major_index into a combinatorial map:

sage: def major_index(p):
....:     return p.major_index()
sage: major_index
<function major_index at ...>
sage: combinatorial_map(major_index)
Combinatorial map: major_index

>>> from sage.all import *
>>> def major_index(p):
...     return p.major_index()
>>> major_index
<function major_index at ...>
>>> combinatorial_map(major_index)
Combinatorial map: major_index
sage.combinat.combinatorial_map.combinatorial_maps_in_class(cls)[source]#

Return the combinatorial maps of the class as a list of combinatorial maps.

For further details and doctests, see Combinatorial maps and combinatorial_map_wrapper().

EXAMPLES:

sage: sage.combinat.combinatorial_map.combinatorial_map = sage.combinat.combinatorial_map.combinatorial_map_wrapper
sage: from importlib import reload
sage: _ = reload(sage.combinat.permutation)
sage: from sage.combinat.combinatorial_map import combinatorial_maps_in_class
sage: p = Permutation([1,3,2,4])
sage: cmaps = combinatorial_maps_in_class(p)
sage: cmaps # random
[Combinatorial map: Robinson-Schensted insertion tableau,
 Combinatorial map: Robinson-Schensted recording tableau,
 Combinatorial map: Robinson-Schensted tableau shape,
 Combinatorial map: complement,
 Combinatorial map: descent composition,
 Combinatorial map: inverse, ...]
sage: p.left_tableau in cmaps
True
sage: p.right_tableau in cmaps
True
sage: p.complement in cmaps
True

>>> from sage.all import *
>>> sage.combinat.combinatorial_map.combinatorial_map = sage.combinat.combinatorial_map.combinatorial_map_wrapper
>>> from importlib import reload
>>> _ = reload(sage.combinat.permutation)
>>> from sage.combinat.combinatorial_map import combinatorial_maps_in_class
>>> p = Permutation([Integer(1),Integer(3),Integer(2),Integer(4)])
>>> cmaps = combinatorial_maps_in_class(p)
>>> cmaps # random
[Combinatorial map: Robinson-Schensted insertion tableau,
 Combinatorial map: Robinson-Schensted recording tableau,
 Combinatorial map: Robinson-Schensted tableau shape,
 Combinatorial map: complement,
 Combinatorial map: descent composition,
 Combinatorial map: inverse, ...]
>>> p.left_tableau in cmaps
True
>>> p.right_tableau in cmaps
True
>>> p.complement in cmaps
True