Opened 11 years ago

Closed 11 years ago

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

Reported by: Owned by: slabbe slabbe major sage-4.6.2 combinatorics sage-combinat, abmasse sage-4.6.2.alpha0 Sébastien Labbé Alexandre Blondin Massé N/A

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

### comment:1 Changed 11 years ago by slabbe

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

### comment:2 follow-up: ↓ 3 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: ↓ 6 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.