Python Program for Generating Lyndon words of length n
Given an integer n and an array of characters S, the task is to generate Lyndon words of length n having characters from S.
A Lyndon word is a string which is strictly less than all of its rotations in lexicographic order. For example, the string β012β is a Lyndon word as it is less than its rotations β120β and β201β, but β102β is not a Lyndon word as it is greater than its rotation β021β.
Note: β000β is not considered to be a Lyndon word as it is equal to the string obtained by rotating it.
Examples:
Input: n = 2, S = {0, 1, 2}
Output: 01
02
12
Other possible strings of length 2 are β00β, β11β, β20β, β21β, and β22β. All of these are either
greater than or equal to one of their rotations.Input: n = 1, S = {0, 1, 2}
Output: 0
1
2
Approach: There exists an efficient approach to generate Lyndon words which was given by Jean-Pierre Duval, which can be used to generate all the Lyndon words upto length n in time proportional to the number of such words. (Please refer to the paper βAverage cost of Duvalβs algorithm for generating Lyndon wordsβ by Berstel et al. for the proof)
The algorithm generates the Lyndon words in a lexicographic order. If w is a Lyndon word, the next word is obtained by the following steps:
- Repeat w to form a string v of length n, such that v[i] = w[i mod |w|].
- While the last character of v is the last one in the sorted ordering of S, remove it.
- Replace the last character of v by its successor in the sorted ordering of S.
For example, if n = 5, S = {a, b, c, d}, and w = βaddβ then we get v = βaddadβ.
Since βdβ is the last character in the sorted ordering of S, we remove it to get βaddaβ
and then replace the last βaβ by its successor βbβ to get the Lyndon word βaddbβ.
Below is the implementation of the above approach:
Python3
# Python implementation of # the above approach n = 2 S = [ '0' , '1' , '2' ] k = len (S) S.sort() # To store the indices # of the characters w = [ - 1 ] # Loop till w is not empty while w: # Incrementing the last character w[ - 1 ] + = 1 m = len (w) if m = = n: print (''.join(S[i] for i in w)) # Repeating w to get a # n-length string while len (w) < n: w.append(w[ - m]) # Removing the last character # as long it is equal to # the largest character in S while w and w[ - 1 ] = = k - 1 : w.pop() |
01 02 12
Please refer complete article on Generating Lyndon words of length n for more details!