生成长度为 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 词最有效的方法。但是，我们已经定制了该方法，使其仅使用数组字符。