在这个问题中，我们将使用数组的字母数字字符查找所有 Lyndon 单词。
在开始之前，让我们先了解一下 Lyndon 一词的定义。
所有单词都是 Lyndon 单词，严格按照字典顺序小于其所有循环。
以下是 Lyndon 单词的示例。
立即学习“Python免费学习笔记（深入）”；
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’。
# Inputn = 2chars = ['c', 'a', 'd']# sort the listinitial_size = len(chars)chars.sort()# Initializing the listindexes = [-1]print("The Lyndon words of length {} is".format(n))# Making iterationswhile 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) 输出
The Lyndon words of length 2 isacadcd
登录后复制
时间复杂度− O(nlogn)，因为我们需要首先对“字符”列表进行排序。
空间复杂度− O(n)，因为我们在列表中存储 n 个索引。
Duval 算法是生成长度为 n 的 Lyndon 词的最有效方法。但是，我们已经自定义了仅使用数组字符的方法。
以上就是生成长度为n的Lyndon单词的Python程序的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2584542.html
