Как распечатать отсортированную перестановку строки с рекурсией в python

Question

Я хочу, чтобы отсортировать перестановки строки отсортированным способом. и мне не разрешено использовать itertools, и я должен сделать это с рекурсией.

это код, который я создал для этой цели, но он очень медленный, так как для 10 символов требуется 200s для печати всех ответов! Я хочу сделать это быстрее, чтобы сделать это за 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 являются 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»). Удачи вам в домашнем задании!