全排列相关问题算法

力扣46、47、60

Posted by songjiu on March 10, 2019

前言

计算permutation问题的整理归纳。

递归求全排列

一般全排列解法使用递归方式,核心思想就是将当前一个数字拿出放入排列池,将剩余数字放进下一次函数递归,递归到排列池长度等于目标长度,返回并将当前排列池作为一个结果。

def dfs(self,list1,res):
        if len(list1)==0:
            return self.result.append(res)
        for i in range(len(list1)):
            self.dfs(list1[0:i]+list1[i+1:],res+list1[i])
def getPermutation(self, n: int, k: int) -> str:
    Solution.result=[]
    list1=''
    for i in range(1,n+1):
        list1+=str(i)
    self.dfs(list1,'')
    return self.result[k-1]

特殊问题求解 力扣60

题目如下:

该题目的特殊性在于,由于他仅仅需要输出第k个全排列,产生全部全排列会提示时间超时,所以采用数学的方式分析,假设当前有n个数字,那么确定他的第k个全排列是什么,可以一位一位的确定。首先要确定首位数字,即1到n共n种可能性,也就是n组,而每组里又有(n-1)!种全排列。所以为了确定第一组(也就是第一位)在什么区间里,要用k除以(n-1)!,商用来确定k位于哪一组,余数就是他在该组的位置,用于计算后续的数字。也就是再去拿余数继续除以(n-2)!,从而确定第二个数字,以此类推。如下:

代码如下:

def getPermutation(self, n: int, k: int) -> str:
        import math
        k-=1
        maplist=[i for i in range(1,n+1)]
        res=''
        temp=0
        while len(maplist)>1:
            n=n-1
            value = math.factorial(n)
            temp=k//(value)
            k=k%value
            res+=str(maplist[temp])
            maplist.pop(temp)
        return res+str(maplist[0])

总结

算法还是弱项,平时做做算法题动动脑子,多积累学习一些必要知识。