Programme Python pour générer des mots Lyndon de longueur n

Dans cette question, nous trouverons tous les mots Lyndon en utilisant un tableau de caractères alphanumériques.

Avant de commencer, comprenons d'abord la définition du mot Lyndon.

• Tous les mots sont des mots Lyndon, strictement lexicographiquement plus petits que tous leurs cycles.

Voici des exemples de mots Lyndon.

• ab - "ab" est strictement lexicographiquement plus petit que toutes ses permutations "ba".

• 89 - La rotation de « 89 » est « 98 », qui est strictement lexicographiquement supérieure à « 89 ».

• abc - Les rotations de 'abc' sont 'bca' et 'cab', qui sont strictement plus grandes que 'abc'.

Voici des exemples de mots non Lyndon.

• aaa - aaa est un mot non Linden car toutes les rotations de "aaa" sont les mêmes.

• bca - « bca » n'est pas un mot Linden car « abc » a une rotation plus petite que lui,

Énoncé du problème- On nous donne un tableau de caractères de longueur K contenant des caractères alphanumériques. De plus, on nous donne n contenant des entiers positifs. La tâche est que nous devons trouver tous les mots Lyndon de longueur n en utilisant les caractères alphanumériques donnés dans le tableau.

Exemple

Entrez

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

Sortie

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

Explication- Il génère tous les mots Lydon de longueur 3 en utilisant des caractères matriciels.

Entrez

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

Sortie

01

Explication- "01" est le seul mot Lyndon que nous pouvons créer en utilisant des 0 et des 1.

Entrez

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

Sortie

ac, ad, cd

Explication- Il génère des mots Lyndon de longueur 2 en utilisant les caractères a, c et d.

Méthode 1

Nous avons un algorithme spécial pour générer des mots Linden appelé algorithme de Duval.

Algorithme

Étape 1- Définissez la valeur "n" qui représente la longueur du mot Lyndon et le tableau de caractères contenant les caractères à utiliser lors de la création du mot Lyndon.

Étape 2- Triez la liste.

Étape 3 − Initialisez la liste "index" avec −1.

Étape 4- Répétez jusqu'à ce que la liste d'index ne soit pas vide.

Étape 5- Augmentez le dernier élément de la liste "index" de 1.

Étape 6− Si list_size est égal à n, imprimez la valeur de la liste.

Étape 7- Ajoutez l'index à la liste afin que sa longueur soit égale à n.

Étape 8- Si le dernier élément de la liste est égal au dernier index du tableau, supprimez-le de la liste.

Exemple

Comprenons l'exemple avec un exemple de saisie.

• La liste triée sera ['a', 'c', 'd'].

• La liste d'index sera mise à jour de [−1] à [0] lors de la première itération. Après cela, la longueur de l'index est égale à 2 et devient [0, 0].

• Dans la deuxième itération, la liste sera mise à jour à [0, 1] et nous trouverons le premier mot Lyndon "ac".

• Dans la troisième itération, la liste deviendra [0, 2] et le deuxième mot Lyndon est "ad". De plus, le dernier élément est supprimé de la liste car il est égal à array_len -1.

• Dans la quatrième itération, la liste deviendra [1]. [1, 1] sera mis à jour ultérieurement.

• À la prochaine itération, la liste deviendra [1, 2] et on retrouve le troisième travail de Lyndon, ''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()

Sortie

The Lyndon words of length 2 is
ac
ad
cd

Complexité temporelle− O(nlogn) car nous devons d'abord trier la liste des "caractères".

Complexité spatiale− O(n) puisque nous stockons n index dans la liste.

L'algorithme Duval est le moyen le plus efficace de générer des mots Lyndon de longueur n. Cependant, nous avons personnalisé la méthode pour utiliser uniquement des caractères de tableau.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!