Improve iterator of word morphisms

[seblabbe]

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

CC: @sagetrac-sage-combinat @saliola

Component: combinatorics

Keywords: words morphisms

Author: Sébastien Labbé, Franco Saliola

Reviewer: Franco Saliola, Sébastien Labbé

Merged: Sage 4.1.2.alpha0

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

[seblabbe]

comment:2

There is a bug in my patch. Some tests are apparently failing....

[seblabbe]

comment:3

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.

[seblabbe]

Attachment: word_iter_morphism_6571-sl.patch.gz

This file depends on #6519 as well as on #5600

[seblabbe]

comment:6

Since #5600 should be merge soon (it has a positive review), I just uploaded a new patch that uses the benefits of #5600.

[saliola]

comment:7

I made a few changes:

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

2. Switched from Compositions to IntegerListsLex instead: the patch converted compositions spit out by Compositions to lists; so I changed it because compositions are created from the lists output by IntegerListsLex.

3. IntegerListsLex allows one to specify min_part, so I added a min_length keyword option (so erasing morphisms can be obtained by taking min_length=0). The default is 1 (the current behaviour).

[saliola]

Apply on top of word_iter_morphism_6571-sl.patch

[saliola]

comment:8

Attachment: trac_6571-reviewer.patch.gz

In case it matters: I applied the patches from #5600 before word_iter_morphism_6571-sl.patch.

[seblabbe]

This patch applies over the precedent two.

[seblabbe]

comment:9

Attachment: trac_6571-seb-review.patch.gz

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

[seblabbe]

Attachment: trac_6571-ReST-bug.patch.gz

Applies over the precedent three patches.

[seblabbe]

comment:10

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.

[saliola]

comment:11

Sébastien's documentation changes are good.

[seblabbe]

Reviewer: Franco Saliola

[seblabbe]

Changed author from Sébastien Labbé to Sébastien Labbé, Franco Saliola

[seblabbe]

Changed reviewer from Franco Saliola to Franco Saliola, Sébastien Labbé

[sagetrac-mvngu]

Merged: Sage 4.1.2.alpha0