Programa en C++ para generar palabras Lyndon de longitud n

Dado un entero n y una array de caracteres S , la tarea es generar palabras Lyndon de longitud n que tengan caracteres de S .

Una palabra de Lyndon es una string que es estrictamente menor que todas sus rotaciones en orden lexicográfico. Por ejemplo, la string “012” es una palabra Lyndon ya que es menor que sus rotaciones “120” y “201”, pero “102” no es una palabra Lyndon ya que es mayor que su rotación “021”.
Nota: “000” no se considera una palabra Lyndon ya que es igual a la string obtenida al rotarla.

Ejemplos:

Entrada: n = 2, S = {0, 1, 2}
Salida: 01
02
12
Otras posibles strings de longitud 2 son «00», «11», «20», «21» y «22». Todos estos son
mayores o iguales a una de sus rotaciones.

Entrada: n = 1, S = {0, 1, 2}
Salida: 0
1
2

Enfoque: existe un enfoque eficiente para generar palabras de Lyndon que fue proporcionado por Jean-Pierre Duval, que se puede usar para generar todas las palabras de Lyndon hasta una longitud n en el tiempo proporcional al número de dichas palabras. (Consulte el artículo “ Coste medio del algoritmo de Duval para generar palabras de Lyndon ” de Berstel et al. para ver la prueba).
El algoritmo genera las palabras de Lyndon en un orden lexicográfico. Si w es una palabra de Lyndon, la siguiente palabra se obtiene mediante los siguientes pasos:

1. Repita w para formar una string v de longitud n , tal que v[i] = w[i mod |w|] .
2. Si bien el último carácter de v es el último en el orden ordenado de S , elimínelo.
3. Reemplace el último carácter de v por su sucesor en el orden ordenado de S.

Por ejemplo, si n = 5, S = {a, b, c, d} y w = «sumar», entonces obtenemos v = «sumar».
Dado que ‘d’ es el último carácter en el orden ordenado de S, lo eliminamos para obtener «adda»
y luego reemplazamos la última ‘a’ por su sucesora ‘b’ para obtener la palabra Lyndon «addb».

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of 
// the above approach 
#include<bits/stdc++.h>
using namespace std;
  
int main()
{
    int n = 2;
    char S[] = {'0', '1', '2' };
    int k = 3;
    sort(S, S + 3);
      
    // To store the indices 
    // of the characters 
    vector<int> w;
    w.push_back(-1);
      
    // Loop till w is not empty     
    while(w.size() > 0)
    {
          
        // Incrementing the last character
        w[w.size()-1]++;
        int m = w.size();
        if(m == n)
        {
            string str;
            for(int i = 0; i < w.size(); i++)
            {
                str += S[w[i]];
            }
            cout << str << endl;
        }
      
        // Repeating w to get a 
        // n-length string
        while(w.size() < n)
        {
            w.push_back(w[w.size() - m]);
        }
      
        // Removing the last character 
        // as long it is equal to 
        // the largest character in S 
        while(w.size() > 0 && w[w.size() - 1] == k - 1)
        {
            w.pop_back();
        }
    }
    return 0;
}
  
// This code is contributed by AdeshSingh1

01
02
12

Consulte el artículo completo sobre Generación de palabras Lyndon de longitud n para obtener más detalles.