Opened 10 years ago

Closed 10 years ago

Last modified 4 years ago

#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 chapoton)

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)

word_iter_morphism_6571-sl.patch (9.6 KB) - added by slabbe 10 years ago.
This file depends on #6519 as well as on #5600
trac_6571-reviewer.patch (7.0 KB) - added by saliola 10 years ago.
Apply on top of word_iter_morphism_6571-sl.patch
trac_6571-seb-review.patch (826 bytes) - added by slabbe 10 years ago.
This patch applies over the precedent two.
trac_6571-ReST-bug.patch (968 bytes) - added by slabbe 10 years ago.
Applies over the precedent three patches.

Download all attachments as: .zip

Change History (19)

comment:1 Changed 10 years ago by slabbe

  • 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 slabbe

  • Summary changed from [with patch, needs review] Improve iterator of word morphisms to [with patch, needs work] Improve iterator of word morphisms

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

comment:3 Changed 10 years ago by slabbe

  • 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 slabbe

  • Cc saliola added

comment:5 Changed 10 years ago by AlexGhitza

  • Component changed from algebra to combinatorics

Changed 10 years ago by slabbe

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

comment:6 Changed 10 years ago by slabbe

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

comment:7 Changed 10 years ago by saliola

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

Changed 10 years ago by saliola

Apply on top of word_iter_morphism_6571-sl.patch

comment:8 Changed 10 years ago by saliola

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

Changed 10 years ago by slabbe

This patch applies over the precedent two.

comment:9 Changed 10 years ago by slabbe

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

Changed 10 years ago by slabbe

Applies over the precedent three patches.

comment:10 Changed 10 years ago by slabbe

  • 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 saliola

Sébastien's documentation changes are good.

comment:12 Changed 10 years ago by slabbe

  • Reviewers set to Franco Saliola

comment:13 Changed 10 years ago by slabbe

  • Authors changed from Sébastien Labbé to Sébastien Labbé, Franco Saliola
  • Reviewers changed from Franco Saliola to Franco Saliola, Sébastien Labbé

comment:14 Changed 10 years ago by mvngu

  • 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 chapoton

  • Description modified (diff)
  • Report Upstream set to N/A
Note: See TracTickets for help on using tickets.