Python program to generate Lyndon words of length n

In this question we will find all Lyndon words using an array of alphanumeric characters.

Before we begin, let us first understand the definition of the word Lyndon.

• All words are Lyndon words, strictly lexicographically smaller than all their cycles.

The following are examples of Lyndon words.

• ab - "ab" is strictly lexicographically smaller than all its permutations "ba".

• 89 - The rotation of ‘89’ is ‘98’, which is strictly lexicographically greater than ‘89’.

• abc - The rotations of 'abc' are 'bca' and 'cab', which are strictly larger than 'abc'.

The following are examples of non-Lyndon words.

• aaa - aaa is a non-Linden word because all rotations of "aaa" are the same.

• bca - 'bca' is a non-Linden word because 'abc' has a smaller rotation than it,

Problem Statement- We are given a character array of length K containing alphanumeric characters. Additionally, we are given n containing positive integers. The task is that we need to find all the Lyndon words of length n using the alphanumeric characters given in the array.

Example

enter

chars = ['1', '3', '2'], n = 3

Output

112, 113, 122, 123, 132, 133, 223, 233

Explanation- It generates all Lydon words of length 3 using array characters.

enter

 n = 2, chars = ['1', '0']

Output

01

Explanation - "01" is the only Lyndon word we can use 0 and 1 to form.

enter

 n = 2, chars = ['c', 'a', 'd']

Output

ac, ad, cd

Explanation- It generates Lyndon words of length 2 using a, c and d characters.

method 1

We have a special algorithm to generate Linden words, called Duval's algorithm.

algorithm

Step 1 - Define the "n" value that represents the length of the Lyndon word and the chars array containing the characters to be used when creating the Lyndon word.

Step 2- Sort the list.

Step 3 − Initialize the "index" list with −1.

Step 4- Iterate until the index list is not empty.

Step 5 - Increase the last element of the "index" list by 1.

Step 6− If list_size is equal to n, print the list value.

Step 7 - Append the index to the list so that its length is equal to n.

Step 8 - If the last element of the list is equal to the last index of the array, remove it from the list.

Example

Let's understand the example with example input.

• The sorted list will be ['a', 'c', 'd'].

• The index list will be updated from [−1] to [0] on the first iteration. After that, the length of the index is equal to 2 and becomes [0, 0].

• On the second iteration, the list is updated to [0, 1] and we find the first Lyndon word "ac".

• On the third iteration the list will become [0, 2] and the second Lyndon word is "ad". Also, the last element is removed from the list because it is equal to array_len -1.

• On the fourth iteration, the list will become [1]. [1, 1] will be updated later.

• On the next iteration the list becomes [1, 2], and we find the third Lyndon wor, ''cd'.

# Input
n = 2
chars = ['c', 'a', 'd']

# sort the list
initial_size = len(chars)
chars.sort()

# Initializing the list
indexes = [-1]

print("The Lyndon words of length {} is".format(n))

# Making iterations
while indexes:
    # Add 1 to the last element of the list
    indexes[-1] += 1
    list_size = len(indexes)

# If the list contains n characters, it means we found a Lyndon word
    if list_size == n:
        print(''.join(chars[p] for p in indexes))

    # Make the list size equal to n by adding characters
    while len(indexes) < n:
        indexes.append(indexes[-list_size])

    while indexes and indexes[-1] == initial_size - 1:
        indexes.pop()

Output

The Lyndon words of length 2 is
ac
ad
cd

Time complexity− O(nlogn), because we need to sort the "character" list first.

Space complexity− O(n) since we store n indexes in the list.

The Duval algorithm is the most efficient way to generate Lyndon words of length n. However, we have customized the method to only use array characters.

The above is the detailed content of Python program to generate Lyndon words of length n. For more information, please follow other related articles on the PHP Chinese website!