生成排列归纳法

假定可以生成前n-1个字符的排列，即可生成前n个字符的排列。
生成s[1:n]的排列，在每个排列前加上s[0];
生成s[1,3,4:n]的排列，在每个排列前加上s[2];
...
重复上述步骤直到生成s[1:n-1]的全部排列,并在每个排列前面加上n

eg.
23 -> 123
32 -> 132

13 -> 213
31 -> 231

12 -> 312
21 -> 321

class Solution:
    def __init__(self):
        self.p=list()
        self.result=list()
    def perl(self,m):
        if m==len(self.p)-1:
            s= ''.join(self.p)
            if s not in self.result:#如果不存在才加入
                self.result.append(s)
        else:
            for j in range(m,len(self.p)):
                self.p[j],self.p[m] = self.p[m],self.p[j] #0-0、 0-1、0-2...1-0、1-1、1-2...互换
                self.perl(m+1)
                self.p[j],self.p[m]=  self.p[m],self.p[j]#每换完一轮要换回来，再进行下一个字符的排列
    def Permutation(self, s):
        self.p=list(s)
        self.perl(0)
        self.result.sort()#按照字典排序
        return self.result

若字符串长度为n且无重复字符,则有n!个排列，递归步骤要执行nn!次，时间复杂度为Θ(nn!)