置换一个字符串打印所有可能的字

-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

来源

2013-03-28 Sandy

你能解决复发关系吗？我忘了怎么做。另外，当你说“排列......打印所有......组合”时，我假设你实际上并不是指组合（因为只有n个组合的n个组合），而是指所有排列组合？鉴于有n！一个字符串在n个不同的（！）字母上的排列，在一般情况下（时间和空间）都不会低于指数复杂度;但是在实际创建排列之前，您可以为每个字符计算出现的次数。 –

说k_i是字符串中字母i的出现次数;事先对外观进行计数（使用直方图的线性时间和空间），您将为“字符串中的所有字符i”保存“product over k_i！”因子（注意阶乘）。 –

@ G.Bach谢谢你的回复，我想这很难再解决，但我同意你的观点，因为这个问题需要所有的排列组合，它不能小于n！并且对于正在运行的程序肯定会有更多的复杂性，但是我的程序的运行时间看起来很糟糕，我猜 – Sandy

正如我在这个问题的评论中提到，在一般情况下，你不会得到下面的指数复杂性，因为对于n不同的角色，有n!排列输入字符串，和O（2 ^ñ）是O（n！）的一个子集。

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

来源

2013-03-28 20:22:36

这是一个好点谢谢！ – Sandy

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

来源

2013-03-28 17:40:18

感谢@约翰的链接我会通读他们，但由于这是一个面试问题，我们需要编写逻辑 – Sandy

置换一个字符串打印所有可能的字

回答

相关问题