生成長度為 n 的 Lyndon 詞的 Python 程式

---

在這個問題中，我們將使用陣列的字母數字字元查詢所有 Lyndon 詞。

在開始之前，讓我們瞭解 Lyndon 詞的定義。

• 所有嚴格小於其所有旋轉的詞都是 Lyndon 詞。

以下是 Lyndon 詞的示例。

• ab − ‘ab’ 嚴格小於其所有排列 ‘ba’。

• 89 − ‘89’ 的旋轉是 ‘98’，它嚴格大於 ‘89’。

• abc − ‘abc’ 的旋轉是 ‘bca’ 和 ‘cab’，它們嚴格大於 ‘abc’。

以下是非 Lyndon 詞的示例。

• aaa − ‘aaa’ 是非 Lyndon 詞，因為 ‘aaa’ 的所有旋轉都相同。

• bca − ‘bca’ 是非 Lyndon 詞，因為其旋轉 ‘abc’ 小於它。

問題陳述− 我們給定一個長度為 K 的字元陣列，其中包含字母數字字元。我們還給定一個正整數 n。任務是需要使用陣列中給定的字母數字字元查詢長度為 n 的所有 Lyndon 詞。

示例

輸入

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

輸出

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

解釋− 它使用陣列字元生成了所有長度為 3 的 Lyndon 詞。

輸入

 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 詞，稱為 Duval 演算法。

演算法

步驟 1− 定義表示 Lyndon 詞長度的 ‘n’ 值和包含在建立 Lyndon 詞時使用的字元的字元陣列。

步驟 2− 對列表進行排序。

步驟 3− 用 -1 初始化 ‘索引’ 列表。

步驟 4− 進行迭代，直到索引列表不為空。

步驟 5− 將 ‘索引’ 列表的最後一個元素加 1。

步驟 6− 如果列表大小等於 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 詞 ‘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)，因為我們最初需要對 ‘chars’ 列表進行排序。

空間複雜度− O(n)，因為我們在列表中儲存 n 個索引。

Duval 演算法是生成長度為 n 的 Lyndon 詞最有效的方法。但是，我們已經定製了該方法，使其僅使用陣列字元。