Generating Lyndon words of length n in Python

By Abinash Reddy

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:

• Get similar words suggestion using Enchant in Python