Generating Lyndon words of length n in Python
In this article, we will learn how to generate Lyndon words of a specified length n in Python. A Lyndon word is a non empty string that is strictly smaller in lexicographix oreder than all of its rotation.
For instance, the string “012” is a Lyndon word as it is not greater than its rotation “120” and “201”, however, “102” isn’t a Lyndon word as it is greater than its rotation “021”.
Note: “000” is not a Lyndon string because it is equal to the string obtained by its rotation.
Generating Lyndon Words
See the given steps below before we go for the coding part:
1. Firstly, declare a list result to store the indices of the characters.
2. Iterate the loop until result is not empty.
- Now increment the last character.
- Repeat the above step until length of result is equal to required length of lyndon word.
- Finally, remove the last characters until it is equal to the largest characters in s.
3. Finally, print the result.
def lyndon_words(s, n): s.sort() result = [-1] k = len(s) while result: result[-1] += 1 m = len(result) if (m == n): print(''.join(s[i] for i in result)) while len(result)<n: result.append(result[-m]) while result and result[-1] == k-1: result.pop() n = int(input("Enter the length of the word: ")) s = ['2', '1', '3', '0'] lyndon_words(s, n)
Output
After we run our program, we can notice the output:
Enter the length of the word: 2 01 02 03 12 13 23 Enter the length of the word: 3 001 002 003 011 012 013 021 022 023 031 032 033 112 113 122 123 132 133 223 233
Also. refer:
Leave a Reply