按字典顺序打印排列

Question

按字典顺序打印字符串的所有排列

我可以只找到一个字符串的所有排列然后对其进行排序吗？这只是时间复杂度 O(n!) -> 查找排列然后对其进行排序是 O(nlogn)（如果快速排序或合并被视为排序算法）。 O(n!)+O(nlogn) 就是复杂度。
geeksforgeeks给出的解决方案 http://www.geeksforgeeks.org/lexicographic-permutations-of-string/ 这表示 O(n*n!)
我在 https://www.educative.io/page/11000001/90001

有人可以解释其中哪一个是最好的，时间复杂度是多少？请解释

Answer 1

如果您确定所有排列然后对其进行排序，那么您的时间复杂度会稍微降低。假设您有一个 n 字符长的字符串。基于从快速搜索 (complexity of recursive string permutation function, Time complexity of this code to list all permutations?) 中找到的一些资源，确定排列的时间复杂度为 Theta(n*n!)

这将生成 n! 不同的排列。现在，要对这些排列进行排序，需要 Theta(n! lg n!)，总时间复杂度为：

Theta(n*n!) + Theta(n! lg n!)

您可以通过构建一个生成排列的算法来消除最后进行昂贵排序的需要，同时保留排序顺序。

我在想象一些递归算法，它将每个连续的字符作为排列的初始字符，然后确定字符串其余部分的排列（也将被排序）。

类似于（部分伪代码，部分 Python）：

def sorted_permute(str):
    if len(str) == 1:
        return [str]
    all_permutations = []
    for pos in len(str):
        next_str = str[:pos] + str[pos+1:]
        permutations = sorted_permute(next_str)
        permutations.prepend_to_all(str[pos])    # This could be expensive
        all_permutations.append(permutations)
    return all_permutations

***** 编辑 *****

如果您不想存储排列，而只想打印排列，您可以执行以下操作：

def sorted_permute(str, head):
    if len(str) == 0:
        print(head)
    for pos in len(str):
        next_str = str[:pos] + str[pos+1:]
        new_head = head + str[pos]
        sorted_permute(next_str, new_head)

按字典顺序打印排列

Print Permutations in lexographical order

algorithm

permutation