Checking if list of integers is a Lyndon word

[geo909]

Hi all,

From wikipedia:

In mathematics, in the areas of combinatorics and computer science, a Lyndon word is a string that is strictly smaller in lexicographic order than all of its rotations. Lyndon words are named after mathematician Roger Lyndon, who introduced them in 1954, calling them standard lexicographic sequences

For example [1,1,2,1,3] is a Lyndon word, but [1,3,1,1,2] is not.

I need to check as efficiently as possible if a given integer sequence is a Lyndon word or not. Is there such an option in sage?
I check the section for Lyndon words in the manual but apparently the only way one can check something like that, is in a
situation like so:

sage: LyndonWord([2,1,2,3])
Traceback (most recent call last):
...
ValueError: Not a Lyndon word

Is this my only option for checking if something is a Lyndon word? This suggests that there is inherently some check in this
function, but I do not want to use a ValueError for that..

Any advice?

Thank you in advance

[Ivan Andrus]

You can use two question marks to see the source code.  You can also edit the source code, so either of the two below should show you what's happening:

LyndonWord??

edit(LyndonWord)

In this case the code of interest is the following:

        super(LyndonWord,self).__init__(parent=LyndonWords(),data=data)

        if check and not self.is_lyndon():

            raise ValueError("Not a Lyndon word")

so it looks like

LyndonWord([2,1,2,3],check=false).is_lyndon()

should do what you want without having to catch a ValueError.

-Ivan

[geo909]

Thanks, that's it! Actually it's even a bit shorter:

a=[2,1,1,3,1,2]
Word(a).is_lyndon()
    False

Thanks a lot.

 

-Ivan

[Andrew]

Dear geo909 (I can't believe what some people call their children!)

Try:

sage: [1,1,2,1,3] in LyndonWords()
True
sage: [2,1,3,2] in LyndonWords()
False

Andrew

[Andrew]

Sorry, I didn't see the later posts.

It turns out that __contains__ in LyndonWords() use a try-except statement to call LyndonWord(). If you're creating a Word() anyway then the Word(*).is_lyndon() test you found will be more efficient.

Andrew