Differences between revisions 1 and 5 (spanning 4 versions)
Revision 1 as of 2009-02-12 17:40:45
Size: 1313
Comment:
Revision 5 as of 2009-02-12 22:43:42
Size: 9833
Comment:
Deletions are marked like this. Additions are marked like this.
Line 3: Line 3:
There are a lot of design issues with concern combinatorial classes.
I'd like to discuss them here. The following are mostly notes from discussion with Nicolas. Once fixed this material should ends in the doc of CombinatorialClass.
There are a lot of design issues which concern combinatorial classes. I'd like to discuss them here. The following are mostly notes from discussion with Nicolas. Once fixed this material should ends in the doc of CombinatorialClass. Please add comment at any places.
Line 8: Line 7:
  The name of the ObjOrientedClasses should be uniform : let's take the example of permutations The name of the ObjOrientedClasses should be uniform : let's take the example of permutations
Line 13: Line 12:
  The following function are standard and should be documented/publicized for all CombClass: The following function are standard and should be documented/publicized for all CombClass:
Line 16: Line 15:
 
  The following function should be written but are not supposed to be called directly by the user:

The following function should be written but are not supposed to be called directly by the user:
Line 24: Line 23:


== Bijection ==
The goal here is to be able to inherits smoothly from a combinatorial class to add extra mathematical structure (eg Poset, Group, Monoid).

 * By default each element created by a combinatorial class should have a parent (Permutations for example).
 * Any element should be constructed by an overloadable function and never by calling directly a class name. {{{_element_constructor}}} seems to be sage default.

A solution is to set two (lazy)_attribute in the combinatorial class named {{{element_class}}} and {{{element_parent}}}



== Bijections ==

When two combinatorial classes As and Bs with object a and b from OOclass A and B are in bijection, there are several possibilities
 * a.to_B() and b.to_A() : this is practical for the user, from the combinatorial point of view. however there is no control on the class nor the parent of the results.
 * As.from_B(b) and Bs.from_A(s) is more consistent. The combinatorial class knows its bijections.
 * Hom(As, Bs).nameOftheBijection(a) ?

It is maybe not a very strong rule. Possible exception A is very standard and B is very exotic. Then maybe one can only write b.to_A() and B.from_A



== Combinatorial Class Factory ==

The goal here is to make is simple to take a subclass of a combinatorial class by adding some constraints. For example if {{{p4=Permutations(4)}}}. The user may want to get the subclass of p4 of permutations of length say 5. So
 - Each combinatorial class should embed the necessary information to rebuild itself with extra constraint.
 - what is the syntax to add this extra constraints ?
   * p4.subclass(length5=5) ?
   * other suggestion ?
 - If no algorithm is known to handles the new constraints what should be the behavior ?
   * raise an error suggesting the user to use a {{{filter}}}
   * do the filter automatically

Here is the copy paste of an old mail from Nicolas which was buried.

{{{
> Factories of combinatorial classes:
>
> There are three levels:
>
> (a) Combinatorial class factories, like:
> Permutations
>
> (b) Combinatorial classes, with list/count operations:
> Permutations(4): models the combinatorial class of permutations of size 4
> Permutations(4, descents = [2,1])
> Permutations(4, greater_than = [3,1,2])
> Permutations(bruhat_smaller=[3,1,2])
> Permutations(left_bruhat_smaller=[3,1,2])
> Permutations(4, left_bruhat_smaller=[3,1,2]): should raise an exception
>
> Those are objects which may be an instance of many classes:
> - Permutations_of_size
> - Permutations_from_descents
> - Permutations_lower_ideal_left_weak_order
> Those classes are implementation details, and need not be known by the user
>
> (c) Data structures for combinatorial objects
> class Permutation, class PermutationArray, class PermutationCycle
>
> Those classes are mostly implementation details
> They define the data structure and algorithms
>
> (d) Combinatorial objects:
> Permutation([1,3,2])
>
> One can always use a combinatorial class CC as constructor; in
> that case, the result c is always an element of CC (i.e. c.parent() = CC)
>
> Example:
> - Permutation([1,2,3]) creates one permutation in Permutations()
> - Permutations(4)([1,2,3,4]) also creates one permutation but this time in Permutations(4)
>
> This might even be the recommended way.
>
> More involved example: tableaux
>
> (a) The Tableaux factory:
> def Tableaux (# size options; only one can be specified?
> size=:, shape
> # content options; only one can be specified
> # standard = True if none is specified?
> standard, alphabet, evaluation, content
> young=True,
> constructor)
>
> Maybe some aliases:
> - def StandardYoungTableaux(*): Tableaux(*,standard=True, parent = StandardYoungTableaux())
> - def SemiStandardYoungTableaux(*): Tableaux(*, parent = StandardYoungTableaux())
>
> (b) Tableaux(4): standard young tableaux of size 4
> Tableaux(shape=[4,1]) standard young tableaux of shape [4,1]
>
> Tableaux(shape=[4,1], evaluation=[3,2])
> Tableaux(shape=[4,1], alphabet=[1,2,4]) : semi standard young tableaux (obtained by crystal operations)
>
> The default parent for the generated tableaux, depends on the young and standard options:
> - Tableaux(standard = True, Young = True)
> - Tableaux(standard=False, Young = True)
> - Tableaux(standard=False, Young = True)
>
>
>
> (c) Data structures for combinatorial objects
> Again, those classes are mostly implementation details
> They define the data structure and algorithms (e.g. RSK will be in YoungTableau)
>
> There may be more than one Tableau data structure (by rows, by
> columns) in which case Tableau is a common abstract class.
>
> (d) Combinatorial objects:
> Tableau([[2,3],[1,2]])
> StandardTableau([[4,3],[1,2]])
> StandardYoungTableau([[3,4],[1,2]])
>
> One can always use a combinatorial class as constructor; this
> might even be the recommended way:
> Tableaux([[2,3],[1,2]])
>
>
> Different data structures and fundamental algorithms for combinatorial objects:
> - Tableau(LabelledObject)
> Indexation choice: t[row,col] with indexing 0 based and longest row first
>
> - from Tableau derives:
> class YoungTableau(Tableau): implements e.g. RSK
> class StandardTableau(Tableau)
> class StandardYoungTableaux(YoungTableau,StandardTableau)
>
> - SkewTableau(LabelledObject) (LabelledObject)
>
> - class AbstractTree(AbstractDigraph)
> Defines precisely the syntax for constructors
>
> - class MyTree(AbstractTree)
>
> ##############################################################################
> Factories, subfactories and subclasses
>
>
> - Consider a factory and a combinatorial class C=Factory(constraints)
> Then C.sub_class(extra_contraints) is the sub class of C satisfying
> simultaneously the constraints for C (including the default ones)
> and the extra_constraints. In practice, this will be constructed by
> calling the factory with all the constraints set.
>
> Consider for example the Tableaux factory (recall that the options
> standard and evaluation are mutually incompatible)
>
> Then, C = Tableaux() models the set of standard tableaux. It is
> equivalent to C=Tableaux(standard=True).
> Now, C.sub_class(evaluation=[3,2]) is *not* Tableaux(evaluation=[3,2])
> but rather Tableaux(standard=True, evaluation=[3,2]) which should
> trigger an error.
>
> ##############################################################################
> Factories as databases of algorithms
>
> The Tableaux factory will typically be implemented using a database like:
> {
> { standard=True, n: "*"} : StandardTableauxBySize
> { standard=True, shape: "*"} : StandardTableauxByShape
> { alphabet: "*", shape: "*"} : SemiStandardTableauxByShapeAndAlphabetCrystal
> }
>
> This allows for two nice features
> - A posteriori extensions of the database by pluging in new algorithm
> - Construction of partially specialized subfactory with
> Tableaux.subfactory(shape="*", alphabet="*")
> to bypass the option checking for those case speed is at a premium
>
> Questions:
>
> - in some cases, we may want to split between the different cases
> differently for counting and listing. Should we support this?
> - does it make sense to define StandardTableaux as
> StandardTableaux = Tableaux.sub_factory(standard=True)
>
>
>
>
> CC = CombinatorialClass
>
> To create the combinatorial classes:
>
> for x in Tableaux(3):
> ...
>
> Comp = Compositions()
> Compositions(4) : CC of elements of Compositions()
> Compositions(4, parent=Compositions(4)) : CC of elements of Compositions(4)
>
> Trees(4, constructor=MyTree) : CC of instances of my_data_structure
>
> Comp.sub_class(4) : returns Compositions(4)
>
> Comp([3,1,2]) : returns the element [3,1,2] of Comp
>
> Arrangements()
>
>
>
> Permutations(4)([1,3,2,4]) : returns an element of Permutations(4)
>
> In general if C is a combinatorial class C(...) returns an element of C
> (Example C=Trees(4))
}}}

Combinatorial Classes

There are a lot of design issues which concern combinatorial classes. I'd like to discuss them here. The following are mostly notes from discussion with Nicolas. Once fixed this material should ends in the doc of CombinatorialClass. Please add comment at any places.

Interface and basic usage

The name of the ObjOrientedClasses should be uniform : let's take the example of permutations

  • the combinatorial class of all permutations should be named Permutations (which is now permutations_all) the __init__ should take in charge to call sub-classes if needed.

  • sub-comb-classes are called Permutations_constraints

  • for the objects one removes the s as in Permutation

The following function are standard and should be documented/publicized for all CombClass:

  • list

  • count is the name fixed ? coherent with the rests of sage ?

The following function should be written but are not supposed to be called directly by the user:

  • __contains__ what should the answer of [2,1,3] in permutations([2,1,3]) ?

  • __iter__ this allows for the class itself to be iterated through. Therefore there is no need for iterator. The former should be deprecated and removed.

Objects/Elements/Parents

The goal here is to be able to inherits smoothly from a combinatorial class to add extra mathematical structure (eg Poset, Group, Monoid).

  • By default each element created by a combinatorial class should have a parent (Permutations for example).
  • Any element should be constructed by an overloadable function and never by calling directly a class name. _element_constructor seems to be sage default.

A solution is to set two (lazy)_attribute in the combinatorial class named element_class and element_parent

Bijections

When two combinatorial classes As and Bs with object a and b from OOclass A and B are in bijection, there are several possibilities

  • a.to_B() and b.to_A() : this is practical for the user, from the combinatorial point of view. however there is no control on the class nor the parent of the results.
  • As.from_B(b) and Bs.from_A(s) is more consistent. The combinatorial class knows its bijections.
  • Hom(As, Bs).nameOftheBijection(a) ?

It is maybe not a very strong rule. Possible exception A is very standard and B is very exotic. Then maybe one can only write b.to_A() and B.from_A

Combinatorial Class Factory

The goal here is to make is simple to take a subclass of a combinatorial class by adding some constraints. For example if p4=Permutations(4). The user may want to get the subclass of p4 of permutations of length say 5. So

  • - Each combinatorial class should embed the necessary information to rebuild itself with extra constraint. - what is the syntax to add this extra constraints ?
    • p4.subclass(length5=5) ?
    • other suggestion ?
    - If no algorithm is known to handles the new constraints what should be the behavior ?
    • raise an error suggesting the user to use a filter

    • do the filter automatically

Here is the copy paste of an old mail from Nicolas which was buried.

> Factories of combinatorial classes:
> 
> There are three levels:
> 
> (a) Combinatorial class factories, like:
>     Permutations
> 
> (b) Combinatorial classes, with list/count operations:
>     Permutations(4): models the combinatorial class of permutations of size 4
>     Permutations(4, descents = [2,1])
>     Permutations(4, greater_than = [3,1,2])
>     Permutations(bruhat_smaller=[3,1,2])
>     Permutations(left_bruhat_smaller=[3,1,2])
>     Permutations(4, left_bruhat_smaller=[3,1,2]): should raise an exception
> 
>     Those are objects which may be an instance of many classes:
>      - Permutations_of_size
>      - Permutations_from_descents
>      - Permutations_lower_ideal_left_weak_order
>     Those classes are implementation details, and need not be known by the user
> 
> (c) Data structures for combinatorial objects
>     class Permutation, class PermutationArray, class PermutationCycle
> 
>     Those classes are mostly implementation details
>     They define the data structure and algorithms
> 
> (d) Combinatorial objects:
>     Permutation([1,3,2])
> 
>     One can always use a combinatorial class CC as constructor; in
>     that case, the result c is always an element of CC (i.e. c.parent() = CC)
> 
>     Example:
>      - Permutation([1,2,3]) creates one permutation in Permutations()
>      - Permutations(4)([1,2,3,4]) also creates one permutation but this time in Permutations(4)
> 
>     This might even be the recommended way.
> 
> More involved example: tableaux
> 
> (a) The Tableaux factory:
>     def Tableaux (# size options; only one can be specified?
>                   size=:, shape
>                   # content options; only one can be specified
>                 # standard = True if none is specified?
>                   standard, alphabet, evaluation, content
>                 young=True,
>                 constructor)
> 
>     Maybe some aliases:
>      - def StandardYoungTableaux(*): Tableaux(*,standard=True, parent = StandardYoungTableaux())
>      - def SemiStandardYoungTableaux(*): Tableaux(*, parent = StandardYoungTableaux())
> 
> (b) Tableaux(4):          standard young tableaux of size 4
>     Tableaux(shape=[4,1]) standard young tableaux of shape [4,1]
> 
>     Tableaux(shape=[4,1], evaluation=[3,2])
>     Tableaux(shape=[4,1], alphabet=[1,2,4]) : semi standard young tableaux (obtained by crystal operations)
> 
>     The default parent for the generated tableaux, depends on the young and standard options:
>      - Tableaux(standard = True, Young = True)
>      - Tableaux(standard=False, Young = True)
>      - Tableaux(standard=False, Young = True)
> 
> 
> 
> (c) Data structures for combinatorial objects
>     Again, those classes are mostly implementation details
>     They define the data structure and algorithms (e.g. RSK will be in YoungTableau)
> 
>     There may be more than one Tableau data structure (by rows, by
>     columns) in which case Tableau is a common abstract class.
> 
> (d) Combinatorial objects:
>     Tableau([[2,3],[1,2]])
>     StandardTableau([[4,3],[1,2]])
>     StandardYoungTableau([[3,4],[1,2]])
> 
>     One can always use a combinatorial class as constructor; this
>     might even be the recommended way:
>     Tableaux([[2,3],[1,2]])
> 
> 
> Different data structures and fundamental algorithms for combinatorial objects:
>  - Tableau(LabelledObject)
>    Indexation choice: t[row,col] with indexing 0 based and longest row first
> 
>  - from Tableau derives:
>     class YoungTableau(Tableau):          implements e.g. RSK
>     class StandardTableau(Tableau)
>     class StandardYoungTableaux(YoungTableau,StandardTableau)
> 
>  - SkewTableau(LabelledObject)       (LabelledObject)
> 
>  - class AbstractTree(AbstractDigraph)
>    Defines precisely the syntax for constructors
> 
>  - class MyTree(AbstractTree)
> 
> ##############################################################################
> Factories, subfactories and subclasses
> 
> 
>  - Consider a factory and a combinatorial class C=Factory(constraints)
>    Then C.sub_class(extra_contraints) is the sub class of C satisfying
>    simultaneously the constraints for C (including the default ones)
>    and the extra_constraints. In practice, this will be constructed by
>    calling the factory with all the constraints set.
> 
>    Consider for example the Tableaux factory (recall that the options
>    standard and evaluation are mutually incompatible)
> 
>    Then, C = Tableaux() models the set of standard tableaux. It is
>    equivalent to C=Tableaux(standard=True).
>    Now, C.sub_class(evaluation=[3,2]) is *not* Tableaux(evaluation=[3,2])
>    but rather Tableaux(standard=True, evaluation=[3,2]) which should
>    trigger an error.
> 
> ##############################################################################
> Factories as databases of algorithms
> 
>    The Tableaux factory will typically be implemented using a database like:
>     {
>       { standard=True, n:     "*"} : StandardTableauxBySize
>       { standard=True, shape: "*"} : StandardTableauxByShape
>       { alphabet: "*", shape: "*"} : SemiStandardTableauxByShapeAndAlphabetCrystal
>     }
> 
>    This allows for two nice features 
>     - A posteriori extensions of the database by pluging in new algorithm
>     - Construction of partially specialized subfactory with
>       Tableaux.subfactory(shape="*", alphabet="*")
>       to bypass the option checking for those case speed is at a premium
> 
>    Questions:
> 
>     - in some cases, we may want to split between the different cases
>       differently for counting and listing. Should we support this?
>     - does it make sense to define StandardTableaux as
>       StandardTableaux = Tableaux.sub_factory(standard=True)
> 
> 
> 
> 
> CC = CombinatorialClass
> 
> To create the combinatorial classes:
> 
> for x in Tableaux(3):
>     ...
> 
> Comp = Compositions()
> Compositions(4)              : CC of elements of Compositions()
> Compositions(4, parent=Compositions(4)) : CC of elements of Compositions(4)
> 
> Trees(4, constructor=MyTree) : CC of instances of my_data_structure
> 
> Comp.sub_class(4)            : returns Compositions(4)
> 
> Comp([3,1,2])                : returns the element [3,1,2] of Comp
> 
> Arrangements()
> 
> 
> 
> Permutations(4)([1,3,2,4]) : returns an element of Permutations(4)
> 
> In general if C is a combinatorial class C(...) returns an element of C
> (Example C=Trees(4))

CombinatorialClass (last edited 2010-02-04 23:36:59 by FlorentHivert)