在這個問題中，我們將使用陣列的字母數字字元來尋找所有 Lyndon 單字。
在開始之前，讓我們先來了解一下 Lyndon 一詞的定義。
所有單字都是 Lyndon 單詞，嚴格按照字典順序小於其所有循環。
以下是 Lyndon 單字的範例。
ab - “ab”嚴格按照字典順序小於其所有排列“ba”。
89 - ‘89’的旋轉是‘98’，嚴格地依照字典順序大於‘89’。
abc - ‘abc’的旋轉是‘bca’和‘cab’，它們嚴格大於‘abc’。
以下是非 Lyndon 單字的範例。
aaa - aaa 是非林登詞，因為「aaa」的所有旋轉都是相同的。
bca - ‘bca’是非林登詞，因為‘abc’它的旋轉比它小，
#問題陳述- 我們給出了一個長度為 K 的字元數組，其中包含字母數字字元。此外，我們也給出了包含正整數的 n。任務是我們需要使用數組中給出的字母數字字元找到長度為 n 的所有 Lyndon 單字。
輸入
chars = ['1', '3', '2'], n = 3
輸出
112, 113, 122, 123, 132, 133, 223, 233
解釋- 它使用陣列字元產生了長度為 3 的所有 Lydon 字。
輸入
n = 2, chars = ['1', '0']
輸出
01
解釋-「01」是我們可以使用 0 和 1 組成的唯一 Lyndon 字。
輸入
n = 2, chars = ['c', 'a', 'd']
輸出
ac, ad, cd
解釋- 它使用 a、c 和 d 字元產生長度為 2 的 Lyndon 單字。
我們有一個特殊的演算法來產生林登詞，稱為杜瓦爾演算法。
第 1 步- 定義代表 Lyndon 單字長度的「n」值和包含建立 Lyndon 單字時要使用的字元的 chars 陣列。
第 2 步- 對清單進行排序。
步驟 3 − 用−1 初始化「索引」清單。
第 4 步- 進行迭代，直到索引清單不為空。
第 5 步- 將「索引」清單的最後一個元素增加 1。
第 6 步− 如果 list_size 等於 n，則列印清單值。
第 7 步- 將索引附加到列表，使其長度等於 n。
第 8 步- 如果清單的最後一個元素等於陣列的最後一個索引，則將其從清單中刪除。
讓我們透過範例輸入來了解範例。
排序後的清單將為 ['a', 'c', 'd']。
索引清單將在第一次迭代中從 [−1] 更新到 [0]。之後索引的長度等於2，變成[0, 0]。
在第二次迭代中，列表將更新為 [0, 1]，我們找到了第一個 Lyndon 單字「ac」。
在第三次迭代中列表將變為 [0, 2]，第二個 Lyndon 單字是「ad」。另外，從清單中刪除最後一個元素，因為它等於 array_len -1。
在第四次迭代中，列表將變成 [1]。之後將更新 [1, 1]。
在下一次迭代中列表將變為 [1, 2]，並且我們找到了第三個 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()
The Lyndon words of length 2 is ac ad cd
時間複雜度− O(nlogn)，因為我們需要先對「字元」清單進行排序。
空間複雜度− O(n)，因為我們在清單中儲存 n 個索引。
Duval 演算法是產生長度為 n 的 Lyndon 字的最有效方法。但是，我們已經自訂了僅使用陣列字元的方法。
以上是產生長度為n的Lyndon單字的Python程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！
