[Python知识库]【一起来刷Python题】——19.解决全排列问题（字节跳动面试题）

?不知不觉调了一天的程序，很多其他的事都还没办，先来做一道算法题吧。坚持，总会有所收获...?

????????从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫作从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。例如输入的字符s=“ABC”，由字符A、B和C组成的全排列为： “ABC”、“ACB”、“BAC”、“BCA”、“CAB”、“CBA”。

程序代码：

def permutation(str):
    lenstr = len(str)
    if lenstr < 2: # 递归边界条件
        return str
    else:
        result = []
        for i in range(lenstr):
            ch = str[i] # 取出每一个字符
            rest = str[0:i] + str[i+1:lenstr]
            for s in permutation(rest): #进行递归
                result.append(ch+s) # 将ch与子问题的解依次组合

    return result
str = input("请输入需要排列字符串：")
print(permutation(str))

字节跳动面试题：递归实现n的全排列

问题描述：输出n个数的全排列。下面是具体要求...

1） 当n=1时，perm(1)=[[1]]；

2） 当n=2时，对于perm(1)里面的灭国list，n可以再list的第0个位置到最后一个位置，这里perm(1)里只有一个子list[1]，所以perm(2)=[[1,2],[2,1]]；

3） 当n=3时，perm(2)的子list有[2,1]和[1,2]，其中对于子list为[2,1]来说，3可以插入到[2,1]的第0个位置到第二个位置，分别是[3,2,1]、[2,3,1]、[2,1,3]，同样对于子list为[1,2]时，可以得到[3,1,2]、[1,3,2]、[1,2,3]。

? ? ? ? 对于perm(n)来说，先去perm(n-1)的每个子列表，然后依次再每个子列表中的每个位置插入n，即可得到perm(n)。

程序代码：

import copy
def perm(n):
    data = []
    if(n==1):
        data.append([1])
    else:
        for m in perm(n-1):
            for j in range(len(m)+1):
                k = copy.copy(m)
                k.insert(j,n)
                data.append(k)
    return data
print(perm(4))