#16935: Faster palindromes function for the Words library
-------------------------+-------------------------------------------------
Reporter: | Owner:
nadialafreniere | Status: new
Type: | Milestone: sage-6.4
enhancement | Keywords: words, finite words,
Priority: major | palindromes
Component: | Authors: Nadia Lafrenière
combinatorics | Report Upstream: N/A
Merged in: | Branch:
Reviewers: | Dependencies:
Work issues: |
Commit: |
Stopgaps: |
-------------------------+-------------------------------------------------
I've written a faster algorithm to get the set of all the distinct
palindromic factors of a given word. There's also a new function called
long_lpc (for long method to get the longest palindome centered at a given
position) that is added.
The principle of the algorithm is to calculate, for every letter and every
space between two letters, the longest palindrome centered in that
position. Once a longer palindrome is found, the information leftwise to
the center is copied to the right because the proper subpalindromes are
present at least twice.
At the same time, there is a list created recording the length of the
longest palindromic suffix of each prefix of the word. Since the number of
prefixes is bounded by one plus the length of the word, the set of
palindromes to be compared is not too big (the comparison is necessary to
get the unicity).
There is still a problem with the palindromes() function already in SAGE
that has not been fixed with the new algorithm : For `f`-palindromes (or
pseudo-palindromes), the word morphism `f` cannot apply to words generated
with the WordGenerator class on the default alphabet (0,1). The main
problem is that the type of the letters of these words are `int` (not
words, nor any type that can be changed into words). I did not find any
way to fix it, except to change the alphabet when generating these words.
{{{
sage: fib=words.FibonacciWord()[:1000]
sage: print "type de fib : " + str(type(fib))
type de fib : <class
'sage.combinat.words.word.FiniteWord_iter_with_caching'>
sage: print "type de fib[5] : " + str(type(fib[5]))
type de fib[5] : <type 'int'>
sage: print "type de words.KolakoskiWord()[2] : " +
str(type(words.KolakoskiWord()[2]))
type de words.KolakoskiWord()[2] : <type 'int'>
sage: print "type de words.ThueMorseWord()[2] : " +
str(type(words.ThueMorseWord()[2]))
type de words.ThueMorseWord()[2] : <type 'int'>
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/16935>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
