TR: [sage-devel] Re: Combinatorics in SAGE

[Vanuxem Grégory]

Just for information, and, could be of interest.

Greg

-----Message d'origine-----
la part de William Stein
Envoyé : vendredi 23 février 2007 22:01
Objet : [sage-devel] Re: Combinatorics in SAGE

The last couple days I've been working on adding a fair amount of
functionality to the combinat module of SAGE. Mostly, I'd like to get
it roughly as feature-complete as mupad-combinat or combinatorica.

Excellent! Also look at the combinatorics functionality in MAGMA and
Maple...

I was wondering the best way to go about integrating these changes
into SAGE, specifically naming conventions. For example, there are
about 75 functions that apply to permuations of the form [1,2,3].
Right now, I just have them in permutation.py in combinat/ and am
importing them all through all.py. Would it be better / more
consistent to just have all.py import permuation and then call the
routines through something like permutation.descents(p) ?

Yes, that would help a lot to not pollute the global namespace
too much. Alternatively, all functions on permutations could
be methods on PermutationGroupElements, which are defined
in sage/groups/perm_gps/. This would be a nice way of unifying
things a bit more, and would make a lot of sense.
If anybody else has any ideas or feedback, please chime in!
--
William Stein
Associate Professor of Mathematics
University of Washington
--~--~---------~--~----~------------~-------~--~----~
To unsubscribe from this group, send email to
For more options, visit this group at

http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and
http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---




-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV

[Martin Rubey]

Dear Prof. Stein,

Gregory forwarded the mail below to me. (Many thanks!) I would like to draw
your attention to the fact, that, together with Ralf Hemmecke I am developing a
package which is related to MuPAD-Combinat. (written in Aldor, compatible with
Axiom) More precisely, it implements "truly", i.e., extremely close to the
mathematical theory, Joyal's "combinatorial species".

This week Ralf has finished the algorithms for the computation of
cycleindexseries of compositions. For example, to generate and enumerate all
binary forests, you can say

B(L: LabelType): CS L == Plus(SingletonSpecies;, Times(B,B))(L) add;
F(L: LabelType): CS L == Compose(SetSpecies, B)(L) add;

(I'm not cheating, that's all)

After this definition

generatingSeries$F gives the (exponential) generating series for
labelled binary forests

isomorphismTypeSeries$F gives the (ordinary) generating series for
unlabelled binary forests

cycleIndexSeries$F gives the cycle index series for binary forests

structures([a,b,c,d)$F produces all binary forests with vertices
labelled a,b,c,d

isomorphismTypes([1,1,2)$F produces all binary forests with vertices
labelled 1,1,2, *not* repeating isomorphic forests


Personally, I have also written a small package that deals with shapes, i.e.,
polyominoes, tableaux, etc., but it is in a *very* early stage of
development. In fact, it is rather experimental, but I think that the ideas are
quite OK. (Well, at least Robinson Schensted Knuth and Jeu de Taquin are
already there...)

Support for combinatorics in Axiom is not so bad. For example, Polya theory is
there. However, it will very likely improve a lot towards the end of this year,
since there will be a Workshop on symmetric functions in June...

I think it would be a shame to redevelop the same things again. If you are
interested in joining us, you are very welcome. Maybe one of you could even
attend the Workshop (June 14 - June 16 ?


Martin


-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV

[Nicolas M. Thiery]

Dear Sage developers,

The last couple days I've been working on adding a fair amount of
functionality to the combinat module of SAGE. Mostly, I'd like to get
it roughly as feature-complete as mupad-combinat or combinatorica.

You are very welcome to get in touch with us
(mupad-combinat-devel-TtF/***@public.gmane.org), and see if we can share anything
(design, user interface, documentation, tests, ...), if not just for
those poor users that will want to switch from one system to another.

How much "man-year" do you expect to put on this project? I mean, it
took us 6 years to develop MuPAD-Combinat. But of course, reusing past
experience, one can hope to go quite faster.

I was wondering the best way to go about integrating these changes
into SAGE, specifically naming conventions. For example, there are
about 75 functions that apply to permuations of the form [1,2,3].
Right now, I just have them in permutation.py in combinat/ and am
importing them all through all.py. Would it be better / more
consistent to just have all.py import permuation and then call the
routines through something like permutation.descents(p) ?

Yes, that would help a lot to not pollute the global namespace
too much. Alternatively, all functions on permutations could
be methods on PermutationGroupElements, which are defined
in sage/groups/perm_gps/. This would be a nice way of unifying
things a bit more, and would make a lot of sense.

I haven't yet checked out the SAGE documentation. Do you have a single
class PermutationGroupElements, or one for each size n?

In MuPAD-Combinat, we have one Dom::SymmetricGroup(n) for each size
n. So, we decided to put the functions on permutations in a separate
domain (e.g. class in MuPAD parlance) combinat::permutations, because
there are a lot of functions that apply to permutations of varying
size (e.g. take a permutation of size m, one of size n, and return a
permutation of size n+m). Also, in many cases, we manipulate
permutations of many different size, and it would not make sense to
instantiate the domain Dom::SymmetricGroup(n) for each of those sizes.
Of course, there are "back links" in Dom::SymmetricGroup(n), albeit
not done automatically yet. Ideally, there probably should be some
hierarchy of categories (abstract class) containing the functions for
manipulating permutations, and various domains for the different use
cases (permutations of a fixed size, with group structure,
permutations of varying size possibly with other structures, ...).

We are having similar issues with trees and tableaux, and are in the
process of reorganizing them accordingly. See in particular:

http://mupad-combinat.sourceforge.net/Wiki/Tableaux

We would love to discuss such issues with others. The axiom workshop
in June is certainly a good occasion for this.

Best regards,
Nicolas

[Martin Rubey]

(I am not subscribed to sage anymore...)

In MuPAD-Combinat, we have one Dom::SymmetricGroup(n) for each size n. So, we
decided to put the functions on permutations in a separate domain (e.g. class
in MuPAD parlance) combinat::permutations, because there are a lot of
functions that apply to permutations of varying size (e.g. take a permutation
of size m, one of size n, and return a permutation of size n+m). Also, in
many cases, we manipulate permutations of many different size, and it would
not make sense to instantiate the domain Dom::SymmetricGroup(n) for each of
those sizes. Of course, there are "back links" in Dom::SymmetricGroup(n),
albeit not done automatically yet. Ideally, there probably should be some
hierarchy of categories (abstract class) containing the functions for
manipulating permutations, and various domains for the different use cases
(permutations of a fixed size, with group structure, permutations of varying
size possibly with other structures, ...).

In Axiom, there is one domain PermutationGroup(S: SetCategory), whose
"elements" are all the subgroups of the permutations of S.

In Aldor it goes witout saying (not in SPAD currently though) that these
elements are again domains, of type Group.

I guess, one really should provide means to specialize to Coxeter groups.

(I just wasted a day or so to implement the things I need for the case of B_n.)

In Axiom, domain instantiation should be very cheap:

(9) -> l := test 5000;

Type: List Any
Time: 0.81 (EV) + 0.03 (OT) + 0.07 (GC) = 0.91 sec
(10) -> l.400

(10) 1
Type: IntegerMod 4601

(Note that the type is correct: IntegerMod 4601)

Martin

-- code: save to "test.spad", compile in axiom with ")co test.spad"
-- did not take time to write clean code.
-- In Aldor, Any becomes unnecessary, fortunately.
)abbrev package TESTG TestGeneration
TestGeneration: Exports == Implementation where

Exports == with

test: PositiveInteger -> List Any

Implementation == add

test n ==
l: List Any := []
for i in 1..n repeat
Z := IntegerMod(i::PositiveInteger)
any1 := AnyFunctions1 Z
l := cons(coerce((i+1)::Z)$any1, l)
l





-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV