#6571 closed enhancement (fixed)
[with patch, positive review] Improve iterator of word morphisms
Reported by: | slabbe | Owned by: | slabbe |
---|---|---|---|
Priority: | major | Milestone: | sage-4.1.2 |
Component: | combinatorics | Keywords: | words morphisms |
Cc: | sage-combinat, saliola | Merged in: | Sage 4.1.2.alpha0 |
Authors: | Sébastien Labbé, Franco Saliola | Reviewers: | Franco Saliola, Sébastien Labbé |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Right now, we can iterate over word morphisms with specific image lengths :
Iterator over morphisms with specific image lengths:: sage: map(str, W.iter_morphisms([2, 1])) ['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'] sage: map(str, W.iter_morphisms([2, 2])) ['WordMorphism: a->aa, b->aa', 'WordMorphism: a->aa, b->ab', 'WordMorphism: a->aa, b->ba', 'WordMorphism: a->aa, b->bb', 'WordMorphism: a->ab, b->aa', 'WordMorphism: a->ab, b->ab', 'WordMorphism: a->ab, b->ba', 'WordMorphism: a->ab, b->bb', 'WordMorphism: a->ba, b->aa', 'WordMorphism: a->ba, b->ab', 'WordMorphism: a->ba, b->ba', 'WordMorphism: a->ba, b->bb', 'WordMorphism: a->bb, b->aa', 'WordMorphism: a->bb, b->ab', 'WordMorphism: a->bb, b->ba', 'WordMorphism: a->bb, b->bb'] sage: map(str, W.iter_morphisms([0, 0])) ['WordMorphism: a->, b->'] sage: map(str, W.iter_morphisms([0, 1])) ['WordMorphism: a->, b->a', 'WordMorphism: a->, b->b']
I want to iterate over all (non erasing) morphisms! In particular, I want the following to work :
sage: W = Words('ab') sage: it = W.iter_morphisms() sage: for _ in range(10): print it.next() 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
Attachments (4)
Change History (19)
comment:1 Changed 10 years ago by
- Status changed from new to assigned
- Summary changed from Improve iterator of word morphisms to [with patch, needs review] Improve iterator of word morphisms
comment:2 Changed 10 years ago by
- Summary changed from [with patch, needs review] Improve iterator of word morphisms to [with patch, needs work] Improve iterator of word morphisms
comment:3 Changed 10 years ago by
- Summary changed from [with patch, needs work] Improve iterator of word morphisms to [with patch, needs review] Improve iterator of word morphisms
Failing tests were related to #5600 because the patch I first posted here was depending on compositions-cleanup-5600-nt.patch
. The patch word_iter_morphism_6571-sl.patch
should now apply cleanly (including doctests) on sage-4.1.1.alpha0.
comment:4 Changed 10 years ago by
- Cc saliola added
comment:5 Changed 10 years ago by
- Component changed from algebra to combinatorics
comment:6 Changed 10 years ago by
comment:7 Changed 10 years ago by
I made a few changes:
- As written, the iter_morphisms method is recursive if it is iterating through all morphisms (it calls
self.iter_morphisms(composition)
for all compositions). This is not necessary and it is inefficient. I changed the code to avoid doing this.
- Switched from
Compositions
toIntegerListsLex
instead: the patch converted compositions spit out byCompositions
to lists; so I changed it because compositions are created from the lists output byIntegerListsLex
.
IntegerListsLex
allows one to specifymin_part
, so I added amin_length
keyword option (so erasing morphisms can be obtained by takingmin_length=0
). The default is 1 (the current behaviour).
comment:8 Changed 10 years ago by
In case it matters: I applied the patches from #5600 before word_iter_morphism_6571-sl.patch.
comment:9 Changed 10 years ago by
Thanks Franco for your good review. I didn't know about IntegerListsLex
. Allowing erasing morphism is great as well. I just added a small patch to correct a word in a one-line comment. I am currently building the documentation...
comment:10 Changed 10 years ago by
- Summary changed from [with patch, needs review] Improve iterator of word morphisms to [with patch, positive review] Improve iterator of word morphisms
There was a bug in the ReST documentation. I just added trac_6571-ReST-bug.patch
which corrects it. Documentation now builds without warnings. Doctests passed on words.py. I am giving a positive review to Franco's changes.
comment:11 Changed 10 years ago by
Sébastien's documentation changes are good.
comment:12 Changed 10 years ago by
- Reviewers set to Franco Saliola
comment:13 Changed 10 years ago by
- Reviewers changed from Franco Saliola to Franco Saliola, Sébastien Labbé
comment:14 Changed 10 years ago by
- Merged in set to Sage 4.1.2.alpha0
- Resolution set to fixed
- Status changed from assigned to closed
comment:15 Changed 4 years ago by
- Description modified (diff)
- Report Upstream set to N/A
There is a bug in my patch. Some tests are apparently failing....