基于字典序算法的全排列

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        # 字典序算法
        # https://www.cnblogs.com/darklights/p/5285598.html
        if not ss:
            return []
        final_list=[ss]
        decrease_list=sorted(list(ss), reverse=True)
        increase_list=sorted(list(ss))
        ss = increase_list
        # 直到降序排列才终止循环
        while ss != decrease_list:
            # 1.从右往左找第一个逆序对ss[i]<ss[i+1]，记录下位置
            for i in list(reversed(range(len(ss)-1))):
                if ss[i]<ss[i+1]:
                    flagi=i
                    break
            # 2.从右往左找第一个比ss[flagi]小的值，记录下位置
            for j in list(reversed(range(flagi, len(ss)))):
                if ss[j]>ss[flagi]:
                    flagj=j
                    break
            # 3.交换flagi 和 flagj的值
            ss[flagi], ss[flagj] = ss[flagj], ss[flagi]
            # 4.对flagi之后的序列排序
            ss=ss[:flagi+1] + sorted(ss[flagi+1:])
            # 恢复成string
            final_list.append(''.join(ss))
        return final_list