Category of classes of combinatorial structures

[sagetrac-elixyre]

That category gives a good and easy pattern of combinatorial structures.

The ideas (a list of others tickets) behind that are

• a simple framework of combinatorial structures
• sum, product, cartesian product, sequence, multi-set, cycle, ...
• species (simplified such that it becomes easy to implement our species of structures)
• change the world (may be)

CC: @nthiery @mantepse @avirmaux

Component: categories

Author: Jean-Baptiste Priez

Branch/Commit: u/elixyre/ticket/16465 @ 7de9abc

Issue created by migration from https://trac.sagemath.org/ticket/16465

[mantepse]

comment:1

It would be very useful to know what difficulties you encounter with the species framework!

Currently, one hold-up for progress regarding species is #16137 and a multivariate companion.

[sagetrac-elixyre]

comment:2

I don't have (especially) problem with the species framework. I have a problem with how to implement a class of combinatorial structures.

The current way to do that consist in copy-paste a file like sage.combinat.binay_trees.py with some obscurs lines then adapt the code.

My patch (when I would tame git) will propose a simple framework to design a class of (combinatorial) structures.

My opinion about species of structures is a species is a class of combinatorial structures! That is a class of combinatorial structures with some specific "method": transport of structures, isomophism types, cycle index series... so in the best of worlds, I want use a species as a parent and I want define more sophisticate structures with its elements.

Furthermore, a set partition, a permutation, ... are structures of a species. It would be nice to merge the module sage.combinat.species. (That will be a second patch...).

About #16137, it seems to me your patch treats generating series but not about the framework of structures, so that is not directly linked. Nowadays, I am not convinced by sage to compute generating series... There exists a deterministic way to define and extract some coefficients in a generating series?? I believe users don't have to learn a new tool to do compute something so LazyPowerSeries, SymbolicRing or whatever must be integrated in an unique manner in sage which one is user friendly...

[sagetrac-elixyre]

Commit: 16685a3

[sagetrac-elixyre]

New commits:

af6f02c	Ticket 16465 : Category of classes of combinatorial structures
16685a3	Ticket 16465 : improve the category and give a framework of class of combinatorial structures

[sagetrac-elixyre]

Branch: u/elixyre/ticket/16465

[mantepse]

comment:5

A comment about a comment in the code: I think it's a misconception that a species is a "labelled structure". Clearly, I can consider every "class of unlabelled structures" as a combinatorial species, albeit possibly not in a very interesting way: simply let the symmetric group act trivially.

[mantepse]

comment:6

Replying to @sagetrac-elixyre:

I don't have (especially) problem with the species framework. I have a problem with how to implement a class of combinatorial structures.

The current way to do that consist in copy-paste a file like sage.combinat.binay_trees.py with some obscurs lines then adapt the code.

I really would like to improve the usability of the species code, to make this task simpler. But I do not yet understand: `binary_trees.py' does not define a species, does it?

I want use a species as a parent and I want define more sophisticate structures with its elements.

Hm. What I'd like to see is a simple way to turn any given parent (eg. `BinaryTree') into a species simply by providing the action of the symmetric group. But I think it's a really bad idea to have something like "species" and something like "combinatorial structures" side by side.

Furthermore, a set partition, a permutation, ... are structures of a species. It would be nice to merge the module sage.combinat.species. (That will be a second patch...).

I'm not sure if I understand.

About #16137, it seems to me your patch treats generating series but not about the framework of structures

quite right (except that it's not my patch). however, it's holding me up from implementing multivariate species, which are necessary to deal with most interesting structures.

I admit that my second big holdup is that I find python a very very very difficult language.

Martin

[sagetrac-elixyre]

comment:7

Replying to @mantepse:

A comment about a comment in the code: I think it's a misconception that a species is a "labelled structure". Clearly, I can consider every "class of unlabelled structures" as a combinatorial species, albeit possibly not in a very interesting way: simply let the symmetric group act trivially.

Ok you are right every class of combinatorial structures is a species (and by default there an trivial action of $S_n$). But my opinion is most of people don't know species and they want only to use/develop class of structures (so roughly a disjoint union of graded set).
It is why I want make a distinction between species and class of combinatorial structures.

Specially one problem if everything is species, that is one has to compute each isomorphism type for every unlabeled class of objects! Most of the time, we have already implemented this class! Furthermore, most of the operation on unlabeled object are well defined: cartesian product, cauchy product, sum, derivation, ... So if someone want use only an unlabeled class it is possible to do it efficiently.

Replying to @mantepse:

I really would like to improve the usability of the species code, to make this task simpler. But I do not yet understand: `binary_trees.py' does not define a species, does it?

I have implemented a really simple example of class of structures in my last commit mod:sage.categories.example.combinatorial_structures_compositions:

16685a3	Ticket 16465 : improve the category and give a framework of class of combinatorial structures

I like this design (not only because it is mine). It is really simple and understandable. If you have any comment... I want.

But I think it's a really bad idea to have something like "species" and something like "combinatorial structures" side by side.

It is a bad idea to make a great distinction between permutations as simple combinatorial objects and permutations as species!
And I don't want them side by side! I want say a species is a refinement of a class of combinatorial structures.

Furthermore, a set partition, a permutation, ... are structures of a species. It would be nice to merge the module sage.combinat.species. (That will be a second patch...).

I'm not sure if I understand.

Sorry my sentence is wrong : "Set partitions, permutations have a (mathematical) structure of species (so both are in the species category)" There is no disadvantage to patch the usual sets as species!

however, it's holding me up from implementing multivariate species, which are necessary to deal with most interesting structures.

I admit that my second big holdup is that I find python a very very very difficult language.

The fact is the Category framework of [comment: nthiery] is really a usefull tool to do that! I want to implementing linear species... but with category, that it is not necessary to reimplement everything from scratch or nearly from. Multivariate, ordered, linear species are species with a refinement of the category after that operations are still same!

Obviously, I understand your problem is not mine, you want enumeration and I want generation! And like I have already say:

There exists a deterministic way to define and extract some coefficients in a generating series??

It was rhetoric... Until that is not user friendly and homogeneous that is not possible to attune enumeration and generation...

[sagetrac-git]

Changed commit from 16685a3 to bb0dcf0

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

bb0dcf0

Ticket 16465 : some operations on classes of combinatorial structures (as unlabelled structures).

[sagetrac-git]

Changed commit from bb0dcf0 to 2a76bb4

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2a76bb4

Ticket 16465 : (unlabelled) sequence of structures

[sagetrac-elixyre]

comment:10

Some of my tests fails in sage.combinat.structures.operations.sequences but I can't reproduce the failure in the terminal. I don't understand that... I believe there is some problem with Categories during the tests. Do you have any idea, [comment: nthiery]?

[sagetrac-git]

Changed commit from 2a76bb4 to 6879bcd

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

6879bcd

Ticket 16465: append cycle and multi set

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4e245dc

Ticket 16465 : fix the bug

[sagetrac-git]

Changed commit from 6879bcd to 4e245dc

[avirmaux]

comment:13

Ummm i fixed some documentation, is it possible to push it without changing the branch ?

[avirmaux]

Changed branch from u/elixyre/ticket/16465 to u/virmaux/ticket/16465

[sagetrac-elixyre]

Changed commit from 4e245dc to 90acf89

[sagetrac-elixyre]

Changed branch from u/virmaux/ticket/16465 to u/elixyre/ticket/16465

[sagetrac-elixyre]

New commits:

ba0f3d0	fixed some documentation
90acf89	Ticket 16465: fix contain in graded component

[sagetrac-git]

Changed commit from 90acf89 to 33395c0

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

33395c0

Ticket 16465: fix graded component of degree 0

[sagetrac-git]

Changed commit from 33395c0 to 58b4ec7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

58b4ec7

Ticket 16465: fix permutation as a class of combinatorial structures

[sagetrac-git]

Changed commit from 58b4ec7 to cab564b

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

55d3d49	Merge branch 't16465' into t16465b
cab564b	Ticket 16465: update documentation

[sagetrac-elixyre]

New commits:

55d3d49	Merge branch 't16465' into t16465b
cab564b	Ticket 16465: update documentation

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2f3e44e

Merge branch 'u/elixyre/ticket/16465' of git://trac.sagemath.org/sage into t16465

[sagetrac-git]

Changed commit from cab564b to 2f3e44e

[sagetrac-git]

Changed commit from 2f3e44e to 68a3da6

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

68a3da6

ticket 16465: fix the documentation of binarytrees

[sagetrac-git]

Changed commit from 68a3da6 to 7de9abc

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7de9abc

ticket 16465: fix some design of combinatorial structure