Opened 13 years ago

Closed 13 years ago

Last modified 7 years ago

#7543 closed enhancement (fixed)

Add S-adic to the word generator

Reported by: Sébastien Labbé Owned by: Sébastien Labbé
Priority: major Milestone: sage-4.3.1
Component: combinatorics Keywords:
Cc: Vincent Delecroix, Franco Saliola Merged in: sage-4.3.1.rc1
Authors: Sébastien Labbé Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Vincent Delecroix)

The definition of S-adic words is found here :

Pytheas S-adiques

This patch adds S-adic to the word generator :

    sage: tm = WordMorphism('a->ab,b->ba')
    sage: fib = WordMorphism('a->ab,b->a')
    sage: from itertools import repeat

One trivial example of infinite s-adic word::

    sage: words.s_adic(repeat(tm),repeat('a'))
    word: abbabaabbaababbabaababbaabbabaabbaababba...

A less trivial infinite s-adic word::

    sage: m = WordMorphism({0:tm,1:fib})
    sage: tmword = words.ThueMorseWord()
    sage: w = m(tmword)
    sage: words.s_adic(w, repeat('a'))
    word: abbaababbaabbaabbaababbaababbaabbaababba...

Random infinite s-adic words::

    sage: from sage.misc.prandom import randint
    sage: def it():
    ...     while True: yield randint(0,1)
    sage: words.s_adic(it(), repeat('a'), [tm,fib])
    word: abbaabababbaababbaabbaababbaabababbaabba...
    sage: words.s_adic(it(), repeat('a'), [tm,fib])

See the patch for more examples.

Attachments (5)

trac_7543_word_s_adiques-sl.patch (16.2 KB) - added by Sébastien Labbé 13 years ago.
trac_7543-review-vd.patch (15.4 KB) - added by Vincent Delecroix 13 years ago.
corrections in documentation string
trac_7543_correction-sl.patch (2.5 KB) - added by Sébastien Labbé 13 years ago.
Applies over the precedent 2 patches.
trac_7543_s_adic_final.patch (16.3 KB) - added by Sébastien Labbé 13 years ago.
Apply only this one.
trac_7543_infinite_alphabet-sl.patch (1.2 KB) - added by Sébastien Labbé 13 years ago.
This patch applies over the above 'final' patch.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 13 years ago by Sébastien Labbé

Status: newneeds_review

comment:2 Changed 13 years ago by Sébastien Labbé

Owner: changed from Mike Hansen to Sébastien Labbé

I just updated the patch (doctest improvements) :

    sage: t = words.ThueMorseWord([tm,fib])
    sage: words.s_adique(t, repeat('a'))
    word: abbaababbaabbaabbaababbaababbaabbaababba...

I am wondering if I should add a #random where I use random examples. Sometimes, other computers gets different random sequence of numbers in the doctest routine...

comment:3 Changed 13 years ago by Sébastien Labbé

I just uploaded the patch. Some more examples. Better doc. The morphisms arguments can now be a callable so that the following works:

    sage: x = lambda h:WordMorphism({1:[2],2:[3]+[1]*(h+1),3:[3]+[1]*h})
    sage: for h in [0,1,2,3]: print h, x(h)
    0 WordMorphism: 1->2, 2->31, 3->3
    1 WordMorphism: 1->2, 2->311, 3->31
    2 WordMorphism: 1->2, 2->3111, 3->311
    3 WordMorphism: 1->2, 2->31111, 3->3111
    sage: w = Word(lambda n : valuation(n+1, 2) ); w
    word: 0102010301020104010201030102010501020103...
    sage: s = words.s_adique(w, repeat(3), x); s
    word: 3232232232322322322323223223232232232232...
    sage: prefixe = s[:10000]
    sage: map(prefixe.number_of_factors, range(15))
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
    sage: [_[i+1] - _[i] for i in range(len(_)-1)]
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Changed 13 years ago by Sébastien Labbé

comment:4 Changed 13 years ago by Vincent Delecroix

Status: needs_reviewpositive_review

Hi Sebastien,

I made the following changes in the documentation and the code seems to be OK.

Take care, Vincent

Changed 13 years ago by Vincent Delecroix

Attachment: trac_7543-review-vd.patch added

corrections in documentation string

comment:5 Changed 13 years ago by Vincent Delecroix

Description: modified (diff)
Reviewers: Vincent Delecroix
Summary: Add S-adiques to the word generatorAdd S-adic to the word generator

comment:6 Changed 13 years ago by Sébastien Labbé

Status: positive_reviewneeds_work

Thanks for the review Vincent. I agree with your changes.

There are two lines that should be keep "s-adiques" : the reference html to pytheas. Will post a patch soon.

comment:7 Changed 13 years ago by Sébastien Labbé

Status: needs_workneeds_review

Vincent, I let you change the status to positive review.

comment:8 Changed 13 years ago by Sébastien Labbé

I just uploaded the corrections patch because I did some doc and sphinx improvements.

Vincent, can you review those small changes I did?

Changed 13 years ago by Sébastien Labbé

Applies over the precedent 2 patches.

comment:9 in reply to:  8 Changed 13 years ago by Vincent Delecroix

Status: needs_reviewpositive_review

Replying to slabbe:

I just uploaded the corrections patch because I did some doc and sphinx improvements.

Vincent, can you review those small changes I did?

The doc is OK. positive review.

comment:10 Changed 13 years ago by Robert Miller

Status: positive_reviewneeds_work
The following tests failed:

        sage -t -long devel/sage-main/sage/combinat/words/word_generators.py # 23 doctests failed
        sage -t -long devel/sage-main/sage/categories/hopf_algebras_with_basis.py # Segfault

Changed 13 years ago by Sébastien Labbé

Apply only this one.

comment:11 Changed 13 years ago by Sébastien Labbé

Authors: Sebastien Labbe
Status: needs_workneeds_review

Sorry for that. There was something depending on patches at #7520. I commented out the offending line and now it should be fine.

Beware, I folded all patches in the same "final" one.

Needs review again!

comment:12 in reply to:  11 ; Changed 13 years ago by Sébastien Labbé

I commented out the offending line and now it should be fine.

Vincent, to help you make the final review, here is what I changed in the patch to correct the failed doctests (the parameter check doesn't exist yet):

- kwds['check'] = False  
+ #kwds['check'] = False 

Beware, I folded all patches in the same "final" one.

Needs review again!

comment:13 in reply to:  12 ; Changed 13 years ago by Vincent Delecroix

Status: needs_reviewneeds_work

In the .identity_morphism() there a big problem with infinite alphabet ! The following will never finish

sage: W = Words(alphabet=Alphabet(name="NN"))
sage: W.identity_morphism()

Anyway, it seems that WordMorphism? is not implemented for infinite alphabet. Could you just raise an Error saying "Not implemented for infinite alphabet" or something like this ?

The rest is OK (I've got no doctesting error with the patch applied on a native 4.3 release)

Changed 13 years ago by Sébastien Labbé

This patch applies over the above 'final' patch.

comment:14 in reply to:  13 ; Changed 13 years ago by Sébastien Labbé

Status: needs_workneeds_review

Anyway, it seems that WordMorphism? is not implemented for infinite alphabet. Could you just raise an Error saying "Not implemented for infinite alphabet" or something like this ?

Done. Thanks for finding this problem. Needs review again!

comment:15 in reply to:  14 Changed 13 years ago by Vincent Delecroix

Status: needs_reviewpositive_review

Knowing that

sage: timeit('W.size_of_alphabet() not in ZZ')
625 loops, best of 3: 24 µs per loop
sage: timeit('W.size_of_alphabet() is Infinity')
625 loops, best of 3: 3.43 µs per loop

We can win 21 micro seconds (at least on my computer) ! As it not important I switch to postive review...

Nice patch this sadic one !

comment:16 Changed 13 years ago by Robert Miller

Merged in: sage-4.3.1.rc1
Resolution: fixed
Status: positive_reviewclosed

comment:17 Changed 7 years ago by Frédéric Chapoton

Authors: Sebastien LabbeSébastien Labbé
Note: See TracTickets for help on using tickets.