![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
This was requested! however all it really entails is a definition...perhaps a redirect? Wikipedia appears to be lacking in general on the broader subject however. Robbjedi 04:45, 18 October 2005 (UTC)
I am not merging this into necklace (combinatorics), as Lyndon word is a standalone concept, deserving its own article. Hope nobody minds. Kompas 09:49, 3 August 2006 (UTC)
needs a reference 173.206.238.69 ( talk) 00:26, 21 May 2012 (UTC)
What's wrong to include the strings "00", "11" etc. in the sequence? -- RokerHRO ( talk) 15:17, 7 July 2014 (UTC)
The algorithm given for computing the standard factorisation looks to be quadratic rather than linear as stated. If the input is 'bbbb...bbba' (n 'b's, 1 'a') then the algorithm takes O(n) time to find the first Lyndon word in the factorisation is 'b', and then it proceeds to factorise 'bbbb...bbba' (with n-1 'b's).
Also, I think the algorithm's finishing condition is faulty, unless it assumes the string ends with a terminating character that's smaller than every other character. As written, 'aa' will factorise as ['aa'] rather than ['a', 'a']. 125.30.89.127 ( talk) 08:59, 3 November 2014 (UTC)
Plus one to faulty finishing condition - from what I gathered one should iterate until the string is empty, and treat m reaching the end of the string as also going to step 3.3.
Also (but that could just be me) I could only understand the algorithm as described after I understood the algorithm already, it isn't clear that it starts with the assumption that a single letter initial Lyndon word is the best it can do and tries proving (3.3) or disproving said assumption by looking at further letters, each time learning a new length assumption for the initial Lyndon word when the previous assumption is proven false (3.2), where equality contributes "nothing".
I also agree with the quadratic runtime assessment, which is most likely due to case 3.3 discarding all accumulated knowledge, though I wouldn't yet know how to do better. 193.227.108.10 ( talk) 13:11, 12 November 2014 (UTC)
def lyndon_factorize(S): start, left, right = 0, 0, 1 while start < len(S): if right == len(S) or S[left] > S[right]: length = right - left while start + length <= right: yield S[start:start+length] start += length left, right = start, start + 1 elif S[left] == S[right]: left, right = left + 1, right + 1 else: left, right = start, right + 1
193.227.108.10 ( talk) 13:15, 13 November 2014 (UTC)
(For starters, English is not my primary language..) My first understanding of this was:
Every binary Lyndon word of each length has its own number.
Probably just my fault, but wouldnt the word amounts be a tiny bit more exact? Although it doesnt sound that good. Or could someone think of another way to say it?
Anyway, if anyone else had trouble understanding, the sequence 1, 2, 1, ... means:
Actually, "amounts" would be a word you'd use for a continuous quantity (a real number like an amount of water) while number makes more sense for discrete integer values (a number of glasses of water). — David Eppstein ( talk) 18:32, 5 November 2014 (UTC)
I have tweaked the definition to regard the empty word as non-Lyndon. There are multiple reasons for this:
Hello fellow Wikipedians,
I have just modified one external link on Lyndon word. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 5 June 2024).
Cheers.— InternetArchiveBot ( Report bug) 18:36, 9 January 2018 (UTC)
![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
This was requested! however all it really entails is a definition...perhaps a redirect? Wikipedia appears to be lacking in general on the broader subject however. Robbjedi 04:45, 18 October 2005 (UTC)
I am not merging this into necklace (combinatorics), as Lyndon word is a standalone concept, deserving its own article. Hope nobody minds. Kompas 09:49, 3 August 2006 (UTC)
needs a reference 173.206.238.69 ( talk) 00:26, 21 May 2012 (UTC)
What's wrong to include the strings "00", "11" etc. in the sequence? -- RokerHRO ( talk) 15:17, 7 July 2014 (UTC)
The algorithm given for computing the standard factorisation looks to be quadratic rather than linear as stated. If the input is 'bbbb...bbba' (n 'b's, 1 'a') then the algorithm takes O(n) time to find the first Lyndon word in the factorisation is 'b', and then it proceeds to factorise 'bbbb...bbba' (with n-1 'b's).
Also, I think the algorithm's finishing condition is faulty, unless it assumes the string ends with a terminating character that's smaller than every other character. As written, 'aa' will factorise as ['aa'] rather than ['a', 'a']. 125.30.89.127 ( talk) 08:59, 3 November 2014 (UTC)
Plus one to faulty finishing condition - from what I gathered one should iterate until the string is empty, and treat m reaching the end of the string as also going to step 3.3.
Also (but that could just be me) I could only understand the algorithm as described after I understood the algorithm already, it isn't clear that it starts with the assumption that a single letter initial Lyndon word is the best it can do and tries proving (3.3) or disproving said assumption by looking at further letters, each time learning a new length assumption for the initial Lyndon word when the previous assumption is proven false (3.2), where equality contributes "nothing".
I also agree with the quadratic runtime assessment, which is most likely due to case 3.3 discarding all accumulated knowledge, though I wouldn't yet know how to do better. 193.227.108.10 ( talk) 13:11, 12 November 2014 (UTC)
def lyndon_factorize(S): start, left, right = 0, 0, 1 while start < len(S): if right == len(S) or S[left] > S[right]: length = right - left while start + length <= right: yield S[start:start+length] start += length left, right = start, start + 1 elif S[left] == S[right]: left, right = left + 1, right + 1 else: left, right = start, right + 1
193.227.108.10 ( talk) 13:15, 13 November 2014 (UTC)
(For starters, English is not my primary language..) My first understanding of this was:
Every binary Lyndon word of each length has its own number.
Probably just my fault, but wouldnt the word amounts be a tiny bit more exact? Although it doesnt sound that good. Or could someone think of another way to say it?
Anyway, if anyone else had trouble understanding, the sequence 1, 2, 1, ... means:
Actually, "amounts" would be a word you'd use for a continuous quantity (a real number like an amount of water) while number makes more sense for discrete integer values (a number of glasses of water). — David Eppstein ( talk) 18:32, 5 November 2014 (UTC)
I have tweaked the definition to regard the empty word as non-Lyndon. There are multiple reasons for this:
Hello fellow Wikipedians,
I have just modified one external link on Lyndon word. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 5 June 2024).
Cheers.— InternetArchiveBot ( Report bug) 18:36, 9 January 2018 (UTC)