在尝试解释递归算法以按字典顺序生成排列时，我提供了这个简单的算法：
def permute(done, remaining):
if not remaining:
print done
return
sorted_rem = sorted(remaining)
l = len(sorted_rem)
for i in xrange(0, l):
c = sorted_rem[i]
# Move to c to done portion.
done.append(c)
remaining.remove(c)
# Permute the remaining
permute(done, remaining)
# Put c back.
remaining.append(c)
# Remove from done.
del done[-1]
def main():
permute([], [1,2,3,4])
if __name__ == "__main__":
main()
第一个问题：这对我来说似乎有点浪费，我想知道它的时间复杂程度是多少 真的有，给定这样的 pythonic 实现吗？
请注意，最佳时间复杂度将是O(n * n!)，因为我们需要打印大小为 n 的 n！ 排列。
我猜测是因为排序(我认为在 python 中是O(n log n))，将添加一个额外的log n因素(我想对于我们可以使用此程序n来说，这几乎可以忽略不计)。
问题的第二部分是对其进行优化。
第二个问题：假设我们可以在
O(n)时间内实现sorted，并且append，remove和del[-1]O(1)时间，结果会是多少 复杂性？
我相信有证据表明运行时确实是O(n*n!).
(灵感来自前面的一个SO问题：递归字符串排列函数的复杂性)
对于所花费的时间，我们有以下递归，无需打印：
T(n) = n*T(n-1) + O(n^2)
现在，如果U(n) = T(n)/n!那么我们必须拥有它
U(n) = U(n-1) + O(n^2/n!)
这是一个伸缩系列。
因此我们得到
U(n) = U(1) + 2^2/2! + 3^2/3! + ... + n^2/n!
使用幂级数进行e^x，乘以x几次，我们看到2^2/2! + 3^2/3! + ... + n^2/n! = O(1)
因此
T(n) = O(n!).
这是不打印所花费的时间。
因此，打印的总时间为O(n * n!).
这也证明了sorted等的运行时间是多少并不重要，只要它们是多项式的，这个算法就是渐近最优的。
常数可能会很糟糕，这就是处理n*n!时真正重要的。
我不知道"pythonic"的做事方式，但我想将一个序列(在数组中给出)转换为下一个字典顺序排列可能比递归构造它更容易(尤其是从收集和排序中多次删除)。下一个排列可以在线性时间中找到，如下所示：
- 查找降序后缀(从末端向后线性扫描)
- 如果后缀前有一个符号(相当于测试当前 POS 是否大于 0)
- 将其与后缀中最小的符号交换(线性扫描或 bsearch)
- 反转后缀(线性)
下面是五个示例的过程的简单可视化。条形指示后缀位置。
12345 - 1234|5 - 1235|4 - 1235|4 - 12354 13452 - 134|52 - 135|42 - 135|24 - 13524 35421 - 3|5421 - 4|5321 - 4|1235 - 41235 54312 - 5431|2 - 5432|1 - 5432|1 - 54321 54321 - |54321 - |54321 - |12345 - 12345
优点：
- 原位处理 - 无需额外的馆藏副本(变量已完成、剩余、sorted_rem)
- 不对集合进行排序，也不删除(删除后压缩)
- 无递归及其堆栈消耗
- 轻松访问结果 - 无需修改代码即可用任何其他
use(done)替换print(done)