algorithm - 按字典顺序打印排列

Question

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

1. 我可以只找到一个字符串的所有排列然后对其进行排序吗？ 这只是时间复杂度 O(n!) -> 对于查找排列然后对其进行排序，它是 O(nlogn)(如果将快速排序或合并视为排序算法)。 O(n!)+O(nlogn) 就是复杂度。

2. geeksforgeeks 给出的解决方案 http://www.geeksforgeeks.org/lexicographic-permutations-of-string/ 这表示为 O(n*n!)

3. 我在 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)