Python 生成长度为n的Lyndon词

在这个问题中，我们将使用数组中的字母数字字符找到所有的Lyndon词。

在开始之前，让我们先了解Lyndon词的定义。

• 所有的词都是Lyndon词，它们在字典排序上严格小于它们所有的旋转。

下面是Lyndon词的示例。

• ab - ‘ab’在所有的排列中严格小于’ba’。

• 89 - ’89’的旋转’98’在字典排序上严格大于’89’。

• abc - ‘abc’的旋转’bca’和’cab’在字典排序上严格大于’abc’。

下面是非Lyndon词的示例。

• aaa - ‘aaa’的所有旋转都相同，所以不是Lyndon词。

• bca - ‘bca’的旋转’abc’小于它自己，所以也不是Lyndon词。

问题陈述 - 给定一个长度为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

我们有一个特殊的算法来生成Lyndon单词，称为Duval算法。

步骤

步骤1 − 定义表示Lyndon单词长度的’n’的值，并包含在创建Lyndon单词时要使用的字符的chars数组。

步骤2 − 对列表进行排序。

步骤3 − 使用-1初始化’indexes’列表。

步骤4 − 迭代直到索引列表不为空。

步骤5 − 将’indexes’列表的最后一个元素增加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单词，’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单词最有效的方法。然而，我们已经定制了这种方法，只使用字符数组。