#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: |
Description (last modified by )
The definition of S-adic words is found here :
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)
Change History (22)
comment:1 Changed 13 years ago by
Status: | new → needs_review |
---|
comment:2 Changed 13 years ago by
Owner: | changed from Mike Hansen to Sébastien Labbé |
---|
comment:3 Changed 13 years ago by
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
Attachment: | trac_7543_word_s_adiques-sl.patch added |
---|
comment:4 Changed 13 years ago by
Status: | needs_review → positive_review |
---|
Hi Sebastien,
I made the following changes in the documentation and the code seems to be OK.
- In english the term is adic (like p-adic numbers)
- I added lines between the item of the INPUT (http://www.sagemath.org/doc/developer/conventions.html#documentation-strings)
Take care, Vincent
Changed 13 years ago by
Attachment: | trac_7543-review-vd.patch added |
---|
corrections in documentation string
comment:5 Changed 13 years ago by
Description: | modified (diff) |
---|---|
Reviewers: | → Vincent Delecroix |
Summary: | Add S-adiques to the word generator → Add S-adic to the word generator |
comment:6 Changed 13 years ago by
Status: | positive_review → needs_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
Status: | needs_work → needs_review |
---|
Vincent, I let you change the status to positive review.
comment:8 follow-up: 9 Changed 13 years ago by
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
Attachment: | trac_7543_correction-sl.patch added |
---|
Applies over the precedent 2 patches.
comment:9 Changed 13 years ago by
Status: | needs_review → positive_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
Status: | positive_review → needs_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
comment:11 follow-up: 12 Changed 13 years ago by
Authors: | → Sebastien Labbe |
---|---|
Status: | needs_work → needs_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 follow-up: 13 Changed 13 years ago by
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 follow-up: 14 Changed 13 years ago by
Status: | needs_review → needs_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
Attachment: | trac_7543_infinite_alphabet-sl.patch added |
---|
This patch applies over the above 'final' patch.
comment:14 follow-up: 15 Changed 13 years ago by
Status: | needs_work → needs_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 Changed 13 years ago by
Status: | needs_review → positive_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
Merged in: | → sage-4.3.1.rc1 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
comment:17 Changed 7 years ago by
Authors: | Sebastien Labbe → Sébastien Labbé |
---|
I just updated the patch (doctest improvements) :
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...