Мой код принимает строку и возвращает список строк, которые являются перестановками входной строки.(Повторений нет)
def perm(slist, c):
rTup = []
for s in slist: #O(n!)
for i in range(len(s) + 1): #O(n)
rstr = s[:i] + c + s[i:] #O(n)
rTup.append(rstr)
return rTup
def permWrap(s): #wrapper
slist = [s]
rlist = [""]
for i in reversed(range(-1,len(s)-1)): #O(n)
rlist = perm(rlist , s[i+1])
return list(set(rlist)) #O(n!)
permWrap("abbc")
Я оставляю мало комментариев о том, что, как мне кажется, сложность времени на каждом этапе.Однако я могу ошибаться.
Я думаю, что временная сложность равна O (n! * N ^ 3).Это правильно?
Кроме того, как бы вы сделали эту функцию более эффективной?