Opened 10 years ago

Closed 10 years ago

#10919 closed enhancement (fixed)

Addition of function ``is_uniform(k)`` for WordMorphism class

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

Status badges

Description

The purpose of this small ticket is to add the function is_uniform(k) to the WordMorphism? class. A morphism m is called k-uniform if for every letter a, we have |m(a)| = k.

For instance, the Thue-Morse morphism a->ab,b->ba is 2-uniform while the Fibonacci morphism a->ab,b->a is not uniform.

Attachments (2)

trac_10919-uniform_morphism-abm.patch (2.0 KB) - added by abmasse 10 years ago.
Apply on sage-4.6.2
trac_10919_review-sl.patch (1.2 KB) - added by slabbe 10 years ago.
Applies over the precedent patch

Download all attachments as: .zip

Change History (7)

Changed 10 years ago by abmasse

Apply on sage-4.6.2

comment:1 Changed 10 years ago by abmasse

  • Authors set to Alexandre Blondin Massé
  • Status changed from new to needs_review

I juste uploaded a patch implementing the ìs_uniform` function. Needs review.

comment:2 Changed 10 years ago by slabbe

With trac_10919-uniform_morphism-abm.patch :

sage: m = WordMorphism(dict(((i,[i]*i) for i in range(30))))     
sage: %timeit m.is_uniform()                                     
625 loops, best of 3: 25.5 µs per loop                           
sage: %timeit m.is_uniform(4)                                    
625 loops, best of 3: 40.6 µs per loop                           

With trac_10919-uniform_morphism-abm.patch and trac_10919_review-sl.patch:

sage: m = WordMorphism(dict(((i,[i]*i) for i in range(30))))   
sage: %timeit m.is_uniform()                                   
625 loops, best of 3: 18 µs per loop                           
sage: %timeit m.is_uniform(4)                                  
625 loops, best of 3: 5.72 µs per loop                                             

Changed 10 years ago by slabbe

Applies over the precedent patch

comment:3 follow-up: Changed 10 years ago by slabbe

  • Reviewers set to Sébastien Labbé

I just uploaded a review patch which, I believe, improves the code.

Other than that, documentation builds fine, all test pass, the new function is OK. If you agree with my small fixes, you can change the status of this ticket to positive review.

comment:4 in reply to: ↑ 3 Changed 10 years ago by abmasse

  • Status changed from needs_review to positive_review

Replying to slabbe:

I just uploaded a review patch which, I believe, improves the code.

Other than that, documentation builds fine, all test pass, the new function is OK. If you agree with my small fixes, you can change the status of this ticket to positive review.

Hi, Sébastien !

Thank you for the review. Once again, you improved the efficiency of my algorithm (I definitely need to be more careful about these small optimisations).

I applied your patch over mine applied over sage-4.6.2 and all tests passed, and the documentation built fine too. Of course, I agree with them, so that I'm ready to set this ticket to positive review.

comment:5 Changed 10 years ago by jdemeyer

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