C++ Program For Generating Lyndon Words Of Length N

In this guide, we are going to explore a C++ code that generates Lyndon Words with a specified length n. Prior to delving into the code, it's essential to have a clear understanding of what Lyndon Words are.

What are Lyndon's Words?

Lyndon strings are sequences that are not empty and possess the quality of being alphabetically smaller than any of their non-trivial permutations. Essentially, a Lyndon string is a sequence that is lesser in value than any of its rearrangements, except for the original sequence itself. Lyndon terms hold significance in the realms of string theory and combinatorics due to this distinct attribute. Their relevance extends to the fields of algorithm analysis, cryptographic techniques, bioinformatics, and data compression because of their distinctive characteristics in factorization.

Sample Example-1:

Input

S = {0, 1} and n = 4

Output

Sample Example-2:

Consider the set of integers {1,2,3}.

Step-1: Produce all feasible words with a length of 1:

1,2,3

Step-2: Produce all feasible combinations of letters with a length of 2:

11,12,13,22,23,33

Step-3: Generate all the possible words of length 3:

• ✅ Starting with 1, append the 1,2,3 to get 111,112,113.
• ✅ Starting with 2, append the 2,3 to get 222,223.
• ✅ Starting with 3, append the 3 to get 333.
• ✅ There is no need to think about any further expansions because the length has been fixed at 3.

Result:

The below list shows the Lyndon words of size 3 generated from the set of numbers {1,2,3}:

111,112,113,222,223,333

Algorithm

Arrange the character array in ascending order by utilizing the sort method.

Initialize a vector named "ch" to keep track of the character indices within the array.

Step 3: To indicate the starting point, the value "-1" is inserted into the "ch" vector.

Using a while loop, iterate through the "ch" vector until its size exceeds zero.

Step 5: Increase the final index in the "ch" array by 1.

Store the size of the "ch" vector in the variable named "ch_size" in Step-6.

To produce a Lyndon word of size "l", display the characters mapped to the indexes in the "ch" array when "ch_size" is set to "1".

Append characters to the "ch" vector iteratively from the same vector until its length is smaller than "l".

If the length of the "ch" vector exceeds zero and the index of the last character in the "ch" vector matches the final index of the array, then eliminate it from the "ch" vector.

Example:

Let's consider an example to produce Lyndon Words of a specific length using C++.

#include <iostream>
#include <vector>
#include <algorithm>
void GeneratingLydonWords(char c[], int arr_len, int l) 
{
    std::sort(c, c + arr_len);	
    std::vector<int> ch;
    ch.push_back(-1);
    while (ch.size() > 0) 
    {
        ch[ch.size() - 1]++;
        int ch_size = ch.size();
        if (ch_size == l)
        {
            std::string temp;
            for (int p = 0; p < ch.size(); p++)
            {
                temp += c[ch[p]];
            }
            std::cout << temp << std::endl;
        }
        while (ch.size() < l)
        {
            ch.push_back(ch[ch.size() - ch_size]);
        }
        while (ch.size() > 0 && ch[ch.size() - 1] == arr_len - 1) 
        {
            ch.pop_back();
        }
    }
}
int main() 
{
    int num_ber;
    std::cout << "Please enter the length of the Lyndon words: ";
    std::cin >> num_ber;
    int arr_len;
    std::cout << "Please enter the length of the characters array: ";
    std::cin >> arr_len;
    char S[arr_len];
    std::cout << "Enter the characters separated by space: ";
    for (int i = 0; i < arr_len; i++) 
    {
        std::cin >> S[i];
    }
    std::cout << "The Lyndon words of length " << num_ber << " are: " << std::endl;
    GeneratingLydonWords(S, arr_len, num_ber);
    return 0;
}

Output:

Please enter the length of the Lyndon words: 2
Please enter the length of the characters array: 3
Enter the characters separated by space: 0 1 2
The Lyndon words of length 2 are: 
01
02
12

Explanation:

This C++ software utilizes a given character array (C) of a specified length (arrlen) to produce Lyndon words of a particular length (number). The characters within the array are arranged in ascending order, and a vector is initialized to hold the indices (ch). It then iterates through all possible combinations of indices to form words. The word is constructed by combining characters from the array based on the indices when the generated word's length matches the required size, and the output is displayed. The software scans characters delimited by spaces, prompts the user for the Lyndon words' length and the character array, and subsequently runs the GeneratingLydonWords function with the provided inputs to generate and exhibit the Lyndon words.

Complexity Analysis:

• ✅ Time complexity - O(NlogN) O(N logN) is the time complexity since sorting the array is required.
• ✅ Space complexity − O(N) The 'ch' array is utilized to store the element's indices, resulting in space complexity of O(N).