置換一個字符串打印所有可能的字

-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

置換一個字符串打印所有可能的字

回答

相關問題