排列算法分析

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列表。你知道吗

def permute(s):
    if len(s) == 1:
        yield s
    else:
        for i, let in enumerate(s):
            for perm in permute(s[:i] + s[i+1:]):
                yield let + perm

for s in permute("abc"):
    print(s)

输出

abc
acb
bac
bca
cab
cba

当然，除非问题需要递归（例如处理递归数据结构，如树），否则最好避免递归（尤其是在Python中）。当然，真正的Python程序通常会使用^{}，除非它需要正确处理基序列中的重复项。在这种情况下，我推荐Narayana Pandita的迭代算法，如this answer所示。你知道吗

Answer 2

最初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]