# 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: