Python-Programm zum Generieren von Lyndon-Wörtern der Länge n

In dieser Frage finden wir alle Lyndon-Wörter mithilfe einer Reihe alphanumerischer Zeichen.

Bevor wir beginnen, wollen wir zunächst die Definition des Wortes Lyndon verstehen.

• Alle Wörter sind Lyndon-Wörter, streng lexikographisch kleiner als alle ihre Zyklen.

Hier sind Beispiele für Lyndon-Wörter.

• ab – „ab“ ist streng lexikographisch kleiner als alle seine Permutationen „ba“.

• 89 – Die Rotation von „89“ ist „98“, was streng lexikographisch größer als „89“ ist.

• abc – Die Rotationen von „abc“ sind „bca“ und „cab“, die unbedingt größer als „abc“ sind.

Das Folgende sind Beispiele für Nicht-Lyndon-Wörter.

• aaa – aaa ist ein Nicht-Linden-Wort, da alle Drehungen von „aaa“ gleich sind.

• bca – „bca“ ist ein Nicht-Linden-Wort, da „abc“ eine kleinere Rotation hat als es,

Problemstellung- Wir erhalten ein Zeichenarray der Länge K, das alphanumerische Zeichen enthält. Zusätzlich erhalten wir n mit positiven ganzen Zahlen. Die Aufgabe besteht darin, dass wir mithilfe der im Array angegebenen alphanumerischen Zeichen alle Lyndon-Wörter der Länge n finden müssen.

Beispiel

Eintreten

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

Ausgabe

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

Erklärung – Es generiert alle Lydon-Wörter der Länge 3 mithilfe von Array-Zeichen.

Eintreten

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

Ausgabe

01

Erklärung- „01“ ist das einzige Lyndon-Wort, das wir aus Nullen und Einsen bilden können.

Eintreten

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

Ausgabe

ac, ad, cd

Erklärung – Es werden Lyndon-Wörter der Länge 2 mit den Zeichen a, c und d generiert.

Methode 1

Wir haben einen speziellen Algorithmus zur Generierung von Linden-Wörtern, den Duval-Algorithmus.

Algorithmus

Schritt 1 – Definieren Sie den „n“-Wert, der die Länge des Lyndon-Worts darstellt, und das chars-Array, das die Zeichen enthält, die beim Erstellen des Lyndon-Worts verwendet werden sollen.

Schritt 2 – Sortieren Sie die Liste.

Schritt 3 − Initialisieren Sie die „Index“-Liste mit −1.

Schritt 4 – Iterieren Sie, bis die Indexliste nicht leer ist.

Schritt 5- Erhöhen Sie das letzte Element der „Index“-Liste um 1.

Schritt 6− Wenn list_size gleich n ist, drucken Sie den Listenwert.

Schritt 7 – Hängen Sie den Index so an die Liste an, dass seine Länge gleich n ist.

Schritt 8 – Wenn das letzte Element der Liste dem letzten Index des Arrays entspricht, entfernen Sie es aus der Liste.

Beispiel

Lassen Sie uns das Beispiel anhand der Beispieleingabe verstehen.

• Die sortierte Liste ist ['a', 'c', 'd'].

• Die Indexliste wird bei der ersten Iteration von [−1] auf [0] aktualisiert. Danach beträgt die Länge des Index 2 und wird zu [0, 0].

• In der zweiten Iteration wird die Liste auf [0, 1] aktualisiert und wir finden das erste Lyndon-Wort „ac“.

• In der dritten Iteration wird die Liste zu [0, 2] und das zweite Lyndon-Wort ist „ad“. Außerdem wird das letzte Element aus der Liste entfernt, da es gleich array_len -1 ist.

• In der vierten Iteration wird die Liste zu [1]. [1, 1] wird später aktualisiert.

• Bei der nächsten Iteration wird die Liste zu [1, 2] und wir finden das dritte Lyndon-Wort, „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()

Ausgabe

The Lyndon words of length 2 is
ac
ad
cd

Zeitkomplexität− O(nlogn), da wir zuerst die „Zeichen“-Liste sortieren müssen.

Raumkomplexität− O(n), da wir n Indizes in der Liste speichern.

Der Duval-Algorithmus ist der effizienteste Weg, Lyndon-Wörter der Länge n zu generieren. Wir haben die Methode jedoch so angepasst, dass nur Array-Zeichen verwendet werden.

Das obige ist der detaillierte Inhalt vonPython-Programm zum Generieren von Lyndon-Wörtern der Länge n. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!