產生長度為n的Lyndon單字的Python程序

在這個問題中，我們將使用陣列的字母數字字元來尋找所有 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

我們有一個特殊的演算法來產生林登詞，稱為杜瓦爾演算法。

演算法

第 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中文網其他相關文章！