如何在python中使用遞歸打印字符串的排序

Question

我想按排序的方式打印字符串的排列。我不能使用itertools，我必須用遞歸來完成。

這是我爲此目的創建的代碼，但它非常緩慢，因爲10個字符需要200秒來打印所有答案！我想讓它在10秒內快速完成。任何幫助？

n = int(input()) # n is the number of characters 

1 <= n <= 10 

elements0 = str(input()) # it will be in this format : A B C D E F G 

elements = elements0.split() 

def translate(elements) : 
    i = 0 
    while i < n : 
     elements[i] = int(i) 
     i = i + 1 
    return elements 

elements = translate(elements) 

def factor(elements,i): 
    elements = elements[:] 
    if i == len(elements) - 1: 
     list.append(elements) 
     return elements 
    else: 
     for j in range(i,len(elements)): 
      elements[i], elements[j] = elements[j], elements[i] 
      factor(elements, i + 1) 
      elements[i], elements[j] = elements[j], elements[i] 

list = [] 

factor(elements,0) 

list = sorted(list) 

def untranslate(list,n) : 
    from math import factorial 
    i = 0 
    while i < factorial(n) : 
     k = 0 
     while k < n : 
      if list[i][k] == 0 : 
       list[i][k] = elements0[0] 
      if list[i][k] == 1 : 
       list[i][k] = elements0[2] 
      if list[i][k] == 2 : 
       list[i][k] = elements0[4] 
      if list[i][k] == 3 : 
       list[i][k] = elements0[6] 
      if list[i][k] == 4 : 
       list[i][k] = elements0[8] 
      if list[i][k] == 5 : 
       list[i][k] = elements0[10] 
      if list[i][k] == 6 : 
       list[i][k] = elements0[12] 
      if list[i][k] == 7 : 
       list[i][k] = elements0[14] 
      if list[i][k] == 8 : 
       list[i][k] = elements0[16] 
      if list[i][k] == 9 : 
       list[i][k] = elements0[18] 
      k = k + 1 
     i = i + 1 
    return list 

list = untranslate(list,n) 



while True : 
    if list == [] : break 
    else: 
     i=0 
     row = str() 
     while i < n : 
      row = row + str(list[0][i]) 
      i = i + 1 
     list.pop(0) 

     print(row) # This should be in this format : ABCDEFG 

和另一點：我要排序的方式不是A B C d ...（字母）。字符的值就像它們出現在元素0中一樣。例如如果元素0是B A，則它必須被打印BA AB。

Answer 1

好吧，既然這是作業，我可以給你一個與你試圖實現的略有不同的版本。

記得在遞歸，你需要兩樣東西：

1. 基本情況
2. 相信自己的功能，這將解決超過基本情況等應有盡有。

下面是代碼

def getPermutations(string): 
    if len(string) == 1: # Base Case 
     return [string] 
    else:    # Not base case 
     result = [] 
     for i in range(len(string)): 
      candidate = string[i] 
      remaining = string[0:i] + string[i+1:] 
      babies = getPermutations(remaining) # Faith! 
      for word in babies: 
       result.append(candidate + word) 
     return result 

這絕對不採取200S爲 「ABCD」。代碼是自我記錄的，所以你應該能夠弄清楚這裏正在做什麼。

下面是一個示例運行。

>>> myPerms = sorted(getPermutations("ABC")) 
>>> for p in myPerms: print p 
... 
ABC 
ACB 
BAC 
BCA 
CAB 
CBA 

請注意，如果字符串有重複的條目（例如「AABC」），這將不起作用。祝你的功課好運！