Opened 11 years ago

Closed 11 years ago

#10134 closed enhancement (fixed)

Provide the enumeration of word morphisms from a range of integers

Reported by: slabbe Owned by: slabbe
Priority: major Milestone: sage-4.6.2
Component: combinatorics Keywords:
Cc: sage-combinat, abmasse Merged in: sage-4.6.2.alpha0
Authors: Sébastien Labbé Reviewers: Alexandre Blondin Massé
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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.

Attachments (3)

trac_10134_iter_morphisms-sl.patch (5.3 KB) - added by slabbe 11 years ago.
trac_10134-review-sl.patch (5.5 KB) - added by slabbe 11 years ago.
Applies over the precedent patch
trac_10134_minor_fixes-abm.patch (803 bytes) - added by abmasse 11 years ago.
Applies on top of the two other patches

Download all attachments as: .zip

Change History (11)

Changed 11 years ago by slabbe

comment:1 Changed 11 years ago by slabbe

  • Authors set to Sébastien Labbé
  • Cc abmasse added
  • Status changed from new to needs_review

comment:2 follow-up: Changed 11 years ago by abmasse

  • Status changed from needs_review to needs_work

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

comment:3 in reply to: ↑ 2 Changed 11 years ago by 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 !?

Changed 11 years ago by slabbe

Applies over the precedent patch

comment:4 Changed 11 years ago by slabbe

  • Status changed from needs_work to needs_review

Needs review!

Changed 11 years ago by abmasse

Applies on top of the two other patches

comment:5 follow-up: Changed 11 years ago by 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.

comment:6 in reply to: ↑ 5 Changed 11 years ago by slabbe

  • Reviewers set to Alexandre Blondin Massé
  • Status changed from needs_review to positive_review

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

I aknowledge.

comment:7 Changed 11 years ago by jdemeyer

  • Milestone changed from sage-4.6.1 to sage-4.6.2

comment:8 Changed 11 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.