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