#9877: Add is_sturmian_factor, is_tangent methods for finite words
-------------------------------+--------------------------------------------
Reporter: tmonteil | Owner: tmonteil
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.6.1
Component: combinatorics | Keywords:
Author: Thierry Monteil | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
Changes (by newvalueoldvalue):
* status: needs_work => needs_review
* author: => Thierry Monteil
Old description:
> Add 3 methods to `sage/combinat/words/finite_word.py`:
>
> 1. sturmian_desubstitute_as_possible
> 1. is_sturmian_factor
> 1. is_tangent
>
> {{{
> sage: w = Word('01110110110111011101',alphabet='01')
> sage: w.is_tangent()
> True
> }}}
New description:
Add 3 methods to `sage/combinat/words/finite_word.py`:
1. sturmian_desubstitute_as_possible
1. is_sturmian_factor
1. is_tangent
Add a protecting `is_tangent` method to `sage/combinat/words/paths.py`.
{{{
sage: w = Word('01110110110111011101',alphabet='01')
sage: w.is_tangent()
True
}}}
--
Comment:
Hi Alexandre,
i started to work back on this ticket. This new patch is supposed to solve
your four points.
Since the `is_tangent()` method can now be applied to a word with more
than 2 letters, i added a protection in the `FiniteWordPath_all` class
into the file `paths.py` so that `is_tangent()` could not be applied for
such word paths. Indeed, there is an extended definition for them, which
is not yet written (see the paper).
Also, concerning a previous comment on using existing sage code, i looked
for some "run" method and the only similar code i found was the
`_delta_iterator()` method in the `Word_class` class. I tried to use it,
but it seems that the use of the `groupby` itertool followed by `len`
makes a slower code:
{{{
from itertools import groupby
def runs_groupby(self):
for letter, run in groupby(self):
yield letter, len(list(run))
def runs_homemade(self):
try:
previous_letter = self[0]
except IndexError:
return
current_run_length = 0
for i in self:
if i == previous_letter:
current_run_length += 1
else:
yield previous_letter , current_run_length
current_run_length = 1
previous_letter = i
yield previous_letter , current_run_length
timeit('for i in runs_groupby(words.FibonacciWord()[:1000]):\n print
i')
timeit('for i in runs_homemade(words.FibonacciWord()[:1000]):\n print
i')
}}}
The first takes 28.6 ms per loop whereas the second takes 18.2 ms per
loop. The problem is that the first method, though more low-level, is like
passing twice on the word, which seems to be slower than the second (high-
level) one-pass method.
Ciao,
Thierry
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9877#comment:13>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
