-1

我写的代码似乎用运行时间和空间的渐近测量看起来很糟糕我得到 T(N) = T(N-1)*N + O((N-1!)*N) 其中 N 是输入的大小。我需要建议优化它

由于这是一个基于算法的面试问题，我们需要在不使用任何库的情况下以最有效的方式实现逻辑

这是我的代码

def str_permutations(str_input,i):
    if len(str_input) == 1:
        return [str_input]
    comb_list = []
    while i < len(str_input):
        key = str_input[i]
        if i+1 != len(str_input):
            remaining_str = "".join((str_input[0:i],str_input[i+1:]))
        else:
            remaining_str = str_input[0:i]
        all_combinations = str_permutations(remaining_str,0)
        for index,value in enumerate(all_combinations):
            all_combinations[index] = "".join((key,value))
        comb_list.extend(all_combinations)
        i = i+1
    return comb_list
4

2 回答 2

2

正如我在对该问题的评论中提到的那样，在一般情况下，您不会低于指数复杂度，因为对于n不同的字符，输入字符串存在n!排列，并且 O(2 n ) 是 O(n!) 的子集.

现在以下内容不会提高一般情况下的渐近复杂度，但您可以优化为具有多次出现的某些字符的字符串生成所有排列的蛮力方法。以字符串为例daedoid；如果你盲目地产生它的所有排列，你会得到每个排列6 = 3!时间，因为你有 3 次出现d. 您可以通过首先消除同一个字母的多次出现并记住使用每个字母的频率来避免这种情况。因此，如果有一个字母c出现 k c，您将保存 k c！排列。因此，总的来说，这为您节省了“产品超过 k c！对于所有 c”的因素。

于 2013-03-28T20:22:36.333 回答
0

如果您不需要自己编写，请参阅itertools.permutations和combinations。

于 2013-03-28T17:40:18.833 回答