python - 置换算法分析

Question

为了一次大面试，我一直在疯狂地研究算法。这种特殊的算法快把我逼疯了，我在一些不理解的行中添加了注释。

def permute(s):
    out = []

    if len(s) == 1:
        # wouldn't setting out replace everything in out?
        out = [s]

    else:
        for i, let in enumerate(s):

            # how does it know that I only want 2 strings?
            for perm in permute(s[:i] + s[i+1:]):

                out += [let + perm]

    return out

print permute("cat")

这个算法的时间复杂度是O(n!)对吗？

Answer 1

最初 out 是在 permute 方法的上下文中定义的，因此每次调用都会有自己的 out 向量。因此，当重新定义 out = [s] 时，您只需覆盖方法上下文中的 out=[]。

如果输入大于一个字符，则会发生这种情况:

# Iterate for each char
for i, let in enumerate(s):
    # Iterate for each permutation of the string without the char i
    for perm in permute(s[:i] + s[i+1:]):
            # Put the removed char in the beginning of the permutation
            # and add it to the list.
            out += [let + perm]