Provide the enumeration of word morphisms from a range of integers #10134

seblabbe · 2010-10-15T22:55:08Z

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.

CC: @sagetrac-sage-combinat @sagetrac-abmasse

Component: combinatorics

Author: Sébastien Labbé

Reviewer: Alexandre Blondin Massé

Merged: sage-4.6.2.alpha0

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

The text was updated successfully, but these errors were encountered:

seblabbe · 2010-10-15T23:18:28Z

Attachment: trac_10134_iter_morphisms-sl.patch.gz

seblabbe · 2010-10-15T23:19:45Z

Author: Sébastien Labbé

sagetrac-abmasse · 2010-11-14T03:31:31Z

comment:2

Hi Sébastien!

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

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.
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.
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
**********************************************************************

seblabbe · 2010-11-14T04:29:59Z

comment:3

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.

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.

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 !?

seblabbe · 2010-11-14T05:04:19Z

Applies over the precedent patch

seblabbe · 2010-11-14T05:05:28Z

comment:4

Attachment: trac_10134-review-sl.patch.gz

Needs review!

sagetrac-abmasse · 2010-11-14T05:42:19Z

Applies on top of the two other patches

sagetrac-abmasse · 2010-11-14T05:44:00Z

comment:5

Attachment: trac_10134_minor_fixes-abm.patch.gz

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.

seblabbe · 2010-11-14T06:14:14Z

comment:6

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

I aknowledge.

seblabbe · 2010-11-14T06:14:14Z

Reviewer: Alexandre Blondin Massé

jdemeyer · 2011-01-12T06:33:49Z

Merged: sage-4.6.2.alpha0

seblabbe added this to the sage-4.6.1 milestone Oct 15, 2010

seblabbe added c: combinatorics labels Oct 15, 2010

seblabbe self-assigned this Oct 15, 2010

seblabbe added the s: needs review label Oct 15, 2010

sagetrac-abmasse mannequin added s: needs work and removed s: needs review labels Nov 14, 2010

seblabbe added s: needs review and removed s: needs work labels Nov 14, 2010

seblabbe added s: positive review and removed s: needs review labels Nov 14, 2010

jdemeyer modified the milestones: sage-4.6.1, sage-4.6.2 Nov 20, 2010

jdemeyer removed the s: positive review label Jan 12, 2011

jdemeyer closed this as completed Jan 12, 2011

fchapoton mentioned this issue Nov 24, 2018

remove a bunch of deprecated renamed keywords #26744

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Provide the enumeration of word morphisms from a range of integers #10134

Provide the enumeration of word morphisms from a range of integers #10134

seblabbe commented Oct 15, 2010

seblabbe commented Oct 15, 2010

seblabbe commented Oct 15, 2010

sagetrac-abmasse mannequin commented Nov 14, 2010

seblabbe commented Nov 14, 2010

seblabbe commented Nov 14, 2010

seblabbe commented Nov 14, 2010

sagetrac-abmasse mannequin commented Nov 14, 2010

sagetrac-abmasse mannequin commented Nov 14, 2010

seblabbe commented Nov 14, 2010

seblabbe commented Nov 14, 2010

jdemeyer commented Jan 12, 2011

Provide the enumeration of word morphisms from a range of integers #10134

Provide the enumeration of word morphisms from a range of integers #10134

Comments

seblabbe commented Oct 15, 2010

seblabbe commented Oct 15, 2010

seblabbe commented Oct 15, 2010

sagetrac-abmasse mannequin commented Nov 14, 2010

seblabbe commented Nov 14, 2010

seblabbe commented Nov 14, 2010

seblabbe commented Nov 14, 2010

sagetrac-abmasse mannequin commented Nov 14, 2010

sagetrac-abmasse mannequin commented Nov 14, 2010

seblabbe commented Nov 14, 2010

seblabbe commented Nov 14, 2010

jdemeyer commented Jan 12, 2011