Enumerate integer vectors modulo the action of a Permutation Group

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

The goal of this ticket is to enumerate integer vectors up to the action of a Permutation Group.

This will produced a Parent : infinite enumerated set whose element are integer vectors (as list of integer)

Apply

• attachment: trac_6812_integer_vectors_mod_permgroup-final.patch
• attachment: trac_6812-reviewer.patch

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: enumeration, integer, list, permutation, group

Author: Nicolas Borie, Simon King

Reviewer: Karl-Dieter Crisman, Simon King, Nicolas Borie

Merged: sage-5.1.beta4

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

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:3

I fixed some language mistakes. I already tell reviewers that there are probably still some typos, misunderstood or mistakes. I am sorry for that... It's hard!

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Description changed:

--- 
+++ 
@@ -4,4 +4,4 @@

 There is a lot of test on this module( strong_generating_system() are also test indirectly in this module... )

-depends on #6647
+depends on #6647 and the category framework #5891

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:5

Refactoring : -> I move the code in sage/combinat/invariant_ring_perm_gps (advise form Nicolas Thiéry) -> I implemented a new class InfiniteEnumeratedSet (with category)

There is no a shortcut in sage to IntegerVectorsUptoPermGroup which is a user friendly parent (with hope). This code stay really strongly connected to the Invariant theory and connected with a the graded algebras of multivariate polynomial view as combination of orbit sum. This really why the code enter this new folder : sage/combinat/invariant_ring_perm_gps (other things have to come here....)

[aghitza]

Changed keywords from enumaration, integer, list, permutation, group to enumeration, integer, list, permutation, group

[simon-king-jena]

comment:10

Hi!

This is not a review yet, just some remarks.

Indeed it seems to me that the comments and the documentation should be proof read by a native speaker. I am not a native speaker, I'm afraid.

I also suggest to rename some methods. For example, the purpose of "generate_list_of_sum" is not clear from that name:

• "generate" suggests a process. Therefore, I expected that the method would return an iterator. But in fact, an actual list is returned. A similar statement applies to "get_orbit". Why not simply "orbit"?
• "list_of_sums" is not clear at all. I mean, there is the notion of "partition", so, there is no reason to describe it as "list of sums". Of course, not all partitions are returned, but representatives for each permutation class of partitions.

So, I think "partition_class_representatives" or slightly less precise "partition_classes" would be clearer.

And "generate_canonicals": The return value is the list of canonical representatives of all children of the input. So, why not "children_representatives" or "canonical_children"?

Best regards, Simon

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:11

Hi Simon,

Thank for these advises, I start a new cleanup and will update a better version shortly!

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Description changed:

--- 
+++ 
@@ -4,4 +4,4 @@

 There is a lot of test on this module( strong_generating_system() are also test indirectly in this module... )

-depends on #6647 and the category framework #5891
+depends on #8288  #6647 and the category framework #5891

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:12

The patch use now the generic code from Search Forest (breadth_first_search....). So this patch now depends on #8288

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Attachment: fast_generating_list_up_to_permgroup-nb.patch.gz

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:13

Add a canonical_representative method... This will perhaps help later...

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Description changed:

--- 
+++ 
@@ -1,7 +1,5 @@
-The goal is to enumerate lists up to the action of a Permutation Group. The final function is generate_list_of_sum(integer) which give all list which sum over all element is the integer.
+The goal of this ticket is to enumerate integer vectors up to the action of a Permutation Group.

-The module in patch use the orderly generating algorithm. The goal is to select list which are maximals according the lexicographic order.
+This will produced a Parent : infinite enumerated set whose element are just tuple of python int (cythonize this is in my wishlist...).

-There is a lot of test on this module( strong_generating_system() are also test indirectly in this module... )
-
-depends on #8288  #6647 and the category framework #5891
+depends on #8288

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:16

Please apply and look only the last patch...

[kcrisman]

comment:17

This looks very interesting, and I could definitely use it in my research (instead of looping over all integer vectors). A few comments:

The syntax seems rather different than IntegerVectors, though; for instance, to access these vectors with a given sum one has to use a fairly awkward notation, instead of something analogous to IntegerVectors(5,6) for those sum 5, length 6. Is it possible to streamline that?

Also, there is fairly non-idiomatic English in some of the docstrings.

Finally, you should put your normal name in the "Author" field, instead of your Trac username, since the script which generates contributor lists uses this information directly.

I am sorry that I am not familiar enough with the category framework to properly review this properly, though :(

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:18

Thanks for your remarks,

I am going to open right now a vote for a better name and access to these class of parents on sage-combinat-devel (and you in CC to vote too).

Feel free to point language mistakes to me! I have to improve my English. Use classical e-mail if you don't want to charge the trac.

Thanks very much, the code will be as much better as it will be used.

Nicolas.

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Changed author from nborie to Nicolas Borie

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:19

I cleaned it, try to correct the language with some help and try to integrate previous advises...

apply trac_6812_integer_vectors_mod_permgroup.patch

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:20

I will clean that after Nicolas (Thiéry) would have review #8288...

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:21

For this last upload :

• Cythonize the is_canonical test
• Change syntax to have IntegerVectorsModPermgroup(G, sum=n) like IntegerVectors or other
• Add a very heavy collection of tests in documentation for developers in the cython part

I feel that my code is not very well polished, but I need advises, corrections and comments. Especially, I hope my English is not too much horrible. Flyspell is well configured on my emacs to american but I don't always use the right words. Sorry for that.

Other things, I know the importance to have good tests in the code. But here, as the method strong_generating_system is very slow, test the module on any group take a very long time (around 3 seconds per group). I will be happy to get some advise and opinion on what deserve to be launch in doctest, what deserve to be kept in comment inside the code and what deserve to be trashed. Currently, the patch present a lot of tests in comments inside the code. It is perhaps too much (or the tests are not the goods one).

[kcrisman]

comment:22

Any reason why you don't just use the tests but with this?

sage: long_test() # long time

It's too much work to remove all the #s anyway if one wanted to try them out.

I like the splitting things into pyx and not. Also, any reason not to incorporate the pyx file into the documentation?

You might want to add a couple examples to the cdef'd functions. I realize this isn't required, but why not? :)

What happens when you list() one of the infinite classes? That should raise an error - I feel like we just had something like this somewhere else, but I can't remember where. Also, you should put an example of how to get elements of the infinite class in the main class, since people may not ever read the documentation for something other than IntegerVectorsModPermutationGroup, which is the one intended to be used by people, right? (It's the only one imported into the global namespace, at any rate.) For this one, I put 'needs work'.

Finally, you are right about the English; there are a few places where I'm not quite sure what is intended, even. But that can be fixed. Keep it up - this will be great! (And very useful for me once I figure out how to use it correctly in my situation.)

[kcrisman]

Reviewer: Karl-Dieter Crisman, Simon King

[kcrisman]

Work Issues: long time tests, information about listing infinite sets

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:23

Thanks a lot for having regarded this...

For # long time, I do not know. I think I will select a subpart of the tests and include them with long time. The developer guide say : "These will not be run regularly during Sage development, but will get run before major releases. No example should take more than about 30 seconds.". Currently, on my three years old macbook, all tests take something like 6 minutes. Especially, there are also # optional - gap_database tests here. I will select some groups and add some tests with long time.

I didn't know we can add pyx file in the doctree, I will add it. I will also add comments on the fact that the is_canonical test is polymorph. I just checked the only thing required is a comparison test:

sage: from sage.combinat.enumeration_mod_permgroup import is_canonical
sage: G = PermutationGroup([[(1,2,3,4,5,6)]])
sage: sgs = [map(lambda x: Permutation(x), trans) for trans in G.strong_generating_system()]
sage: is_canonical(sgs, ['c','b','a','b','b','a'])
True
sage: is_canonical(sgs, [3,2,1,2,2,1])
True

As string can be compared with < and >, the function can be also used on such object.

I think that examples in cdef functions aren't required just because one cannot import them in the sage console. Try from file.pyx import . There is perhaps another way to import them, but I don't know...

For the behavior of list(), I think it is ok. The category framework do the job:

sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]))
sage: list(I)
...
NotImplementedError: infinite list
sage: I = IntegerRange(1,+Infinity, 5)
sage: I
{1, 6, ..}
sage: list(I)
...
NotImplementedError: infinite list
sage: I = InfiniteEnumeratedSets().example()
sage: I
An example of an infinite enumerated set: the non negative integers
sage: list(I)
...
NotImplementedError: infinite list

I going to improve the doc of IntegerVectorsModPermutationGroup. You're definitely right and I think it deserves to stay the only entrance point for this module.

Thanks for your comments.

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Description changed:

--- 
+++ 
@@ -1,5 +1,7 @@
 The goal of this ticket is to enumerate integer vectors up to the action of a Permutation Group.

-This will produced a Parent : infinite enumerated set whose element are just tuple of python int (cythonize this is in my wishlist...).
+This will produced a Parent : infinite enumerated set whose element are integer vectors (as list of integer)
+
+apply: [attachment: trac_6812_integer_vectors_mod_permgroup.patch](https://github.com/sagemath/sage-prod/files/10645939/trac_6812_integer_vectors_mod_permgroup.patch.gz)

 depends on #8288

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:25

Ok, I tried to include all previous remarks...

I would say also that it is one of my first time with cython (I don't know if it is very well done...). This version integrate the tests with some with decorators long time.

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:26

I put a needs work because we must set on sage-combinat-devel if we plan to refactor integer vector as hashable type...

I mainly implement this object to create an algebra whose basis is indexed by orbit_sum of monomial. But CombinatorialFreeModule requires hashable elements as basis keys. There is a choice here and I don't have the language overview to decide such direction.

[kcrisman]

comment:27

Just a question, as I've returned to the research where this could be helpful...

I see at this link that this stuff appears to actually be in the combinat branch already? If so, is it possible that the 'needs work' issue has been resolved?

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:28

As SearchForest as been integrated, let me one or two weeks (and FPSAC...) to finalize this... Stay in the area if you want to give review to this work. Feel free to give some comments, requests or advises especially if you have also use cases on this features.

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Description changed:

--- 
+++ 
@@ -2,6 +2,6 @@

 This will produced a Parent : infinite enumerated set whose element are integer vectors (as list of integer)

-apply: [attachment: trac_6812_integer_vectors_mod_permgroup.patch](https://github.com/sagemath/sage-prod/files/10645939/trac_6812_integer_vectors_mod_permgroup.patch.gz)
+apply [attachment: trac_6812_integer_vectors_mod_permgroup.patch](https://github.com/sagemath/sage-prod/files/10645939/trac_6812_integer_vectors_mod_permgroup.patch.gz)

 depends on #8288

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:29

I cleaned the imports, I improved a little the documentation...

I am very sorry but it needs a STRONG REVIEW OF ENGLISH. My flyspell is well configured in my emacs but I feel that there are probably some not very well expressed sentences in my documentation. I tried to do my best... About the code, it is strongly tested, there is a lot of tests of consistences with other parts of combinat.

nicolas@lancelot:/opt/sage/devel/sage-combinat$ sage -t sage/combinat/integer_vectors_mod_permgroup.py -optional -long
sage -t -optional -long "devel/sage-combinat/sage/combinat/integer_vectors_mod_permgroup.py"
     [10.3 s]

----------------------------------------------------------------------
All tests passed!
Total time for all tests: 10.3 seconds
nicolas@lancelot:/opt/sage/devel/sage-combinat$ sage -t sage/combinat/enumeration_mod_permgroup.pyx -optional -long
sage -t -optional -long "devel/sage-combinat/sage/combinat/enumeration_mod_permgroup.pyx"
     [38.5 s]

----------------------------------------------------------------------
All tests passed!
Total time for all tests: 38.5 seconds

apply trac_6812_integer_vectors_mod_permgroup.patch (only)

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:30

It depends on something in the sage combinat queue...

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Description changed:

--- 
+++ 
@@ -4,4 +4,4 @@

 apply [attachment: trac_6812_integer_vectors_mod_permgroup.patch](https://github.com/sagemath/sage-prod/files/10645939/trac_6812_integer_vectors_mod_permgroup.patch.gz)

-depends on #8288
+depends on #10335

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:31

Ok, it depends on #10335

la pile de patchs est maintenant vide
nicolas@lancelot:/opt/sage/devel/sage-review$ hg qpush
application de trac_10334-permgroup_cleanup-rebase-mh.patch
actuellement à : trac_10334-permgroup_cleanup-rebase-mh.patch
nicolas@lancelot:/opt/sage/devel/sage-review$ hg qpush
application de trac_10335-permgroup_domain-mh.patch
actuellement à : trac_10335-permgroup_domain-mh.patch
nicolas@lancelot:/opt/sage/devel/sage-review$ hg qpush
application de trac_6812_integer_vectors_mod_permgroup.patch
actuellement à : trac_6812_integer_vectors_mod_permgroup.patch
nicolas@lancelot:/opt/sage/devel/sage-review$ sage -b
...
nicolas@lancelot:/opt/sage/devel/sage-review$ sage -t sage/combinat/enumeration_mod_permgroup.pyx 
sage -t  "devel/sage-review/sage/combinat/enumeration_mod_permgroup.pyx"
     [14.3 s]

----------------------------------------------------------------------
All tests passed!
Total time for all tests: 14.3 seconds
nicolas@lancelot:/opt/sage/devel/sage-review$ sage -t sage/combinat/integer_vectors_mod_permgroup.py 
sage -t  "devel/sage-review/sage/combinat/integer_vectors_mod_permgroup.py"
     [5.7 s]

----------------------------------------------------------------------
All tests passed!
Total time for all tests: 5.7 seconds

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Dependencies: #10335

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Changed dependencies from #10335 to #10335, #10334

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Description changed:

--- 
+++ 
@@ -4,4 +4,4 @@

 apply [attachment: trac_6812_integer_vectors_mod_permgroup.patch](https://github.com/sagemath/sage-prod/files/10645939/trac_6812_integer_vectors_mod_permgroup.patch.gz)

-depends on #10335
+depends on #10335, #10334

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:35

After a big big rush on thesis finalization, I will try to dealt with this ticket as soon as possible... With all the comments that Karl-Dieter sent to me 4 months ago, I should be able to propose something interesting shortly.

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Description changed:

--- 
+++ 
@@ -3,5 +3,3 @@
 This will produced a Parent : infinite enumerated set whose element are integer vectors (as list of integer)

 apply [attachment: trac_6812_integer_vectors_mod_permgroup.patch](https://github.com/sagemath/sage-prod/files/10645939/trac_6812_integer_vectors_mod_permgroup.patch.gz)
-
-depends on #10335, #10334

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Changed dependencies from #10335, #10334 to none

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:36

The last version should be ready for review.

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:37

please patchbot,

apply only attachment: trac_6812_integer_vectors_mod_permgroup.patch

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:38

Second try for the buildbot:

apply trac_6812_integer_vectors_mod_permgroup.patch

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:39

Ok, it can't apply... I am sick of human dependencies coming from sharing a Mercurial queue... Sorry for all spam!

[jasongrout]

comment:40

Are you talking about this patch depending on something in the combinat queue?

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:41

Yes, precisely.

All works fine on the queue and I really spent a lot of time on that. But some patches (before me in the queue) and supposed to have the status "Needs review" on the trac make this patch can be apply (typically, file like '\modules_list' or '\doc\bla\foo' are concerned). As It was late in the night and I was tired, realize It doesn't work make me a little angry. Sorry for that.

I will finalize it on a separate branch as much of Sage contributors usually do.

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:42

apply trac_6812_integer_vectors_mod_permgroup.patch

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:43

All tests pass with -long and -optinal on the sage-combinat repository. I think the problems come from the two dependencies.

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

Dependencies: #10334, #10335

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:44

Why does want the patchbot applies systematically the two patches... Where should I put the following line to make the patchbot remember it permanently ?

apply trac_6812_integer_vectors_mod_permgroup.patch

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:45

This deserves a proper refactoring with ClonableIntArray...

A new version is on the way.

[simon-king-jena]

comment:46

Hi Nicolas!

Some questions: When we met in Orsay, we discussed some speed-ups of your code. Are they part of the attached patch? And couldn't one say that for now the patch needs review, and the transition to ClonableIntArray can be done on a different ticket? It would be nice to have the stuff in Sage, finally!