按字典序打印排列

Question

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

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

2. geeksforgeeks提供的解决方案称其为O(n*n!)。请参考链接：http://www.geeksforgeeks.org/lexicographic-permutations-of-string/ 3. 我在https://www.educative.io/page/11000001/90001上找到了另一种解决方案。

请问哪种方法最好并且时间复杂度是多少？请解释。

- Sahithi

---

暴力破解应该是O(n!)，除非你可以以某种方式修改排列生成算法，在不进行额外工作的情况下拒绝非排序字符串。 - Tim Biegeleisen

暴力破解是一种生成排列并对其进行排序的方法吗？ - Sahithi

无法拒绝任何字符串。每个单独的字符串未排序，但在打印之前对该字符串的所有排列进行了排序。 - arewm

为什么要对所有排列进行排序？你可以先对输入字符串进行排序，然后生成排列，如果正确执行，它们将自动按字典顺序排列。 - maraca

Answer 1

如果你确定所有排列然后进行排序，那么你的时间复杂度有点偏差。假设你有一个长度为n的字符串。根据一些快速搜索到的资源（递归字符串排列函数的复杂度, 列出所有排列的代码的时间复杂度？），确定排列的时间复杂度为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)

- arewm

---

谢谢你们的解释，真的帮了我很多 :) - Sahithi

@user3519495 没问题。如果有帮助的话，我添加了一个算法的伪代码。 - arewm

for (i=0; i<N; i++) { for(j=i; j<N; j++) { s = input.substring(i, j); if (!list.hasItem(s)) { list.addItem(s); }}} 当输入已排序时，此操作将对列表进行字典序排序。 - maraca

没有必要存储排列，OP想要打印它们。此外，复杂度有更紧密的界限O(e.n!)，我认为... - Kedar Mhaswade

@user3519495 时间复杂度将包括排序和排列，对吗？我认为排列的时间复杂度是O(nn!)，但这不能简化为O(n!)。因此，时间复杂度将为O(nn!)。 - arewm