Provide the enumeration of word morphisms from a range of integers

[slabbe]

The method iter_morphisms may iterate through all morphisms (infinite iterator) or through all morphisms having particular lengths for the image of each letter. Recently, I needed something in the middle, that is, a finite iterator that behaves like the infinite one. Thus, I added a new possible type for the argument (tuple) which specifies a range for the sum of the lengths of the images. Here is an example:

    sage: W = Words('ab')
    sage: for m in W.iter_morphisms( (2, 4) ): print m
    WordMorphism: a->a, b->a
    WordMorphism: a->a, b->b
    WordMorphism: a->b, b->a
    WordMorphism: a->b, b->b
    WordMorphism: a->aa, b->a
    WordMorphism: a->aa, b->b
    WordMorphism: a->ab, b->a
    WordMorphism: a->ab, b->b
    WordMorphism: a->ba, b->a
    WordMorphism: a->ba, b->b
    WordMorphism: a->bb, b->a
    WordMorphism: a->bb, b->b
    WordMorphism: a->a, b->aa
    WordMorphism: a->a, b->ab
    WordMorphism: a->a, b->ba
    WordMorphism: a->a, b->bb
    WordMorphism: a->b, b->aa
    WordMorphism: a->b, b->ab
    WordMorphism: a->b, b->ba
    WordMorphism: a->b, b->bb

Patch to be posted soon.

[abmasse]

Hi Sébastien!

I took a look at your patch. It should be easy to review but I still have some comments:

1. I dislike the parameter name l for two reasons. First, it might be confused with the digit 1. Second, because it is not significant. I suggest you use the name lengths or order_iterating, well, anything else more significant.
2. The possible values for l are quite confusing. List means something, tuple, something else... I don't know if there's a more understandable interface that could be offered. Maybe there could be a parameter lengths_interval or fixed_lengths, etc. that could distinguish the different cases.
3. The sentence "The length of the list must be the number of letters in the alphabet, and the i-th integer of l determines the length of the word mapped to by the i-th letter of the (ordered) alphabet" is not very clear. Maybe it would be better to describe it with mathematical expressions (although it's harder to read in terminal mode). I would suggest something simpler such as : "If l is a list, then it describes the length of the images for each letter of the morphism."

I know my ideas aren't very clear, but maybe it could still inspire you into improving the docstring. I'll wait for your answer to resume the review. Note also that I get some doctest failures:

**********************************************************************
File "/Users/alexandre/Applications/sage/devel/sage-t10134/sage/combinat/words/words.py", line 1138:
    sage: for m in W.iter_morphisms((0, 3), min_length=0): print m
Expected:
    WordMorphism: a->, b->
    WordMorphism: a->a, b->
    WordMorphism: a->b, b->
    WordMorphism: a->, b->a
    WordMorphism: a->, b->b
    WordMorphism: a->aa, b->
    WordMorphism: a->ab, b->
    WordMorphism: a->ba, b->
    WordMorphism: a->bb, b->
    WordMorphism: a->a, b->a
    WordMorphism: a->a, b->b
    WordMorphism: a->b, b->a
    WordMorphism: a->b, b->b
    WordMorphism: a->, b->aa
    WordMorphism: a->, b->ab
    WordMorphism: a->, b->ba
    WordMorphism: a->, b->bb
Got:
    WordMorphism: a->, b->aaa
    WordMorphism: a->, b->aab
    WordMorphism: a->, b->aba
    WordMorphism: a->, b->abb
    WordMorphism: a->, b->baa
    WordMorphism: a->, b->bab
    WordMorphism: a->, b->bba
    WordMorphism: a->, b->bbb
**********************************************************************
File "/Users/alexandre/Applications/sage/devel/sage-t10134/sage/combinat/words/words.py", line 1159:
    sage: for m in W.iter_morphisms( (2, 4) ): print m
Expected:
    WordMorphism: a->a, b->a
    WordMorphism: a->a, b->b
    WordMorphism: a->b, b->a
    WordMorphism: a->b, b->b
    WordMorphism: a->aa, b->a
    WordMorphism: a->aa, b->b
    WordMorphism: a->ab, b->a
    WordMorphism: a->ab, b->b
    WordMorphism: a->ba, b->a
    WordMorphism: a->ba, b->b
    WordMorphism: a->bb, b->a
    WordMorphism: a->bb, b->b
    WordMorphism: a->a, b->aa
    WordMorphism: a->a, b->ab
    WordMorphism: a->a, b->ba
    WordMorphism: a->a, b->bb
    WordMorphism: a->b, b->aa
    WordMorphism: a->b, b->ab
    WordMorphism: a->b, b->ba
    WordMorphism: a->b, b->bb
Got:
    WordMorphism: a->aa, b->aaaa
    WordMorphism: a->aa, b->aaab
    WordMorphism: a->aa, b->aaba
    WordMorphism: a->aa, b->aabb
    WordMorphism: a->aa, b->abaa
    WordMorphism: a->aa, b->abab
    WordMorphism: a->aa, b->abba
    WordMorphism: a->aa, b->abbb
    WordMorphism: a->aa, b->baaa
    WordMorphism: a->aa, b->baab
    WordMorphism: a->aa, b->baba
    WordMorphism: a->aa, b->babb
    WordMorphism: a->aa, b->bbaa
    WordMorphism: a->aa, b->bbab
    WordMorphism: a->aa, b->bbba
    WordMorphism: a->aa, b->bbbb
    WordMorphism: a->ab, b->aaaa
    WordMorphism: a->ab, b->aaab
    WordMorphism: a->ab, b->aaba
    WordMorphism: a->ab, b->aabb
    WordMorphism: a->ab, b->abaa
    WordMorphism: a->ab, b->abab
    WordMorphism: a->ab, b->abba
    WordMorphism: a->ab, b->abbb
    WordMorphism: a->ab, b->baaa
    WordMorphism: a->ab, b->baab
    WordMorphism: a->ab, b->baba
    WordMorphism: a->ab, b->babb
    WordMorphism: a->ab, b->bbaa
    WordMorphism: a->ab, b->bbab
    WordMorphism: a->ab, b->bbba
    WordMorphism: a->ab, b->bbbb
    WordMorphism: a->ba, b->aaaa
    WordMorphism: a->ba, b->aaab
    WordMorphism: a->ba, b->aaba
    WordMorphism: a->ba, b->aabb
    WordMorphism: a->ba, b->abaa
    WordMorphism: a->ba, b->abab
    WordMorphism: a->ba, b->abba
    WordMorphism: a->ba, b->abbb
    WordMorphism: a->ba, b->baaa
    WordMorphism: a->ba, b->baab
    WordMorphism: a->ba, b->baba
    WordMorphism: a->ba, b->babb
    WordMorphism: a->ba, b->bbaa
    WordMorphism: a->ba, b->bbab
    WordMorphism: a->ba, b->bbba
    WordMorphism: a->ba, b->bbbb
    WordMorphism: a->bb, b->aaaa
    WordMorphism: a->bb, b->aaab
    WordMorphism: a->bb, b->aaba
    WordMorphism: a->bb, b->aabb
    WordMorphism: a->bb, b->abaa
    WordMorphism: a->bb, b->abab
    WordMorphism: a->bb, b->abba
    WordMorphism: a->bb, b->abbb
    WordMorphism: a->bb, b->baaa
    WordMorphism: a->bb, b->baab
    WordMorphism: a->bb, b->baba
    WordMorphism: a->bb, b->babb
    WordMorphism: a->bb, b->bbaa
    WordMorphism: a->bb, b->bbab
    WordMorphism: a->bb, b->bbba
    WordMorphism: a->bb, b->bbbb
**********************************************************************

[slabbe]

1. I dislike the parameter name l for two reasons. First, it might be confused with the digit 1. Second, because it is not significant. I suggest you use the name lengths or order_iterating, well, anything else more significant.

OK. The parameter l could be changed. I agree. But, to keep it backward compatible, we still need to support l. Maybe arg would be more adapted.

1. The possible values for l are quite confusing. List means something, tuple, something else... I don't know if there's a more understandable interface that could be offered. Maybe there could be a parameter lengths_interval or fixed_lengths, etc. that could distinguish the different cases.

I disagree on that. It is not C code, it is python. For example, it is OK to do :

sage: Permutation((5,3,2,4,1))   # tuple means cycle notation
[5, 4, 2, 1, 3]
sage: Permutation([5,3,2,4,1])   # list means images of [1, 2, 3, 4, 5] in that order
[5, 3, 2, 4, 1]

The problems with many arguments like lengths_interval or fixed_lengths is (1) you still need to look at the documentation to use and understand those arguments, (2) you need to type the name of those argument everytime you use them and (3) the code needs to consider inconsistencies, that is, if both argument are defined by the user.

1. The sentence "The length of the list must be the number of letters in the alphabet, and the i-th integer of l determines the length of the word mapped to by the i-th letter of the (ordered) alphabet" is not very clear. Maybe it would be better to describe it with mathematical expressions (although it's harder to read in terminal mode). I would suggest something simpler such as : "If l is a list, then it describes the length of the images for each letter of the morphism."

I suggest :

"The length of the list must be equal to the size of the alphabet, and the i-th integer of l determines the length of the word mapped to by the i-th letter of the (ordered) alphabet"

Note also that I get some doctest failures:

I do not get those doctest failures. Did you rebuild your branch !?

[slabbe]

Applies over the precedent patch

[slabbe]

Needs review!

[abmasse]

Applies on top of the two other patches

[abmasse]

I tested the two patches on sage-4.6 and all tests passed. The documentation looked fine, except for a typo I corrected in a review patch.

I'm ready to set this ticket to positive review as soon as Sébastien acknowledge my review patch.

[slabbe]

I'm ready to set this ticket to positive review as soon as Sébastien acknowledge my review patch.

I aknowledge.