python中自带的排列:

itertools.permutations(iterable,r=None)

功能：连续返回由iterable序列中的元素生成的长度为r的排列

如果r未指定或为None，r默认设置未iterable的长度，即生成包含所有元素的全排列

from itertools import permutations
s = ['a','b','c']
for element in permutations(s,2):
    a = element[0] + element[1]
    # 或者这样写: a = ''.join(element)
    print(a,end=' ')
# 输出 ab ac ba bc ca cb 

       permutations()是按元素的位置顺序输出的元素的排列，也就是说，输出的排列的顺序是位置的字典序。例如s=[‘b’,’a’,’c’]，执行permutations(s)，输出“bac bca abc acb cba cab”，并不是按字符的字典序输出排列，而是按位置顺序输出。

       s = [‘b’,’a’,’c’]的3个元素的位置是’b’=1、’a’=2、’c’=3，输出的排列”bac bca abc acd cba cad”，按位置表示就是”123 132 213 231 312 321″，这是按从小到大的顺序输出的。

python中自带的组合:

组合函数与排列函数相似,但是元素无序

from itertools import combinations
s = ['1','2','3']
for element in combinations(s,2):
    a = ''.join(element)
    print(a,end=' ')
# 输出 12 13 23 

       由于自带的排列和组合效率比较低，所以我们需要进行手写排列组合，必要时进行剪枝等操作，进行优化。

 手写排列和组合：

dfs参数有两种:一种是全局变量，另一种是形参

递归问题要手动画一个递归搜索树，有利于加深理解。

递归实现指数型枚举:

思路: 按顺序从1~n依次考虑每个数选与不选

n = int(input())
st = [0] * 16 # st 记录每一位的状态，选与不选
def dfs(u): # u 表示当前第几位
    if u == n:
        for i in range(n):
            if st[i] == 1:
                print(i+1,end=" ")
        print()
        return 
    st[u] = 1
    dfs(u+1)
    st[u] = 0
    dfs(u+1)
dfs(0)

递归实现排列型枚举：

思路1：依次枚举每个数放到哪个位置

思路2：依次枚举每个位置放哪个数

n = int(input())
st = [0] * (n+1)
used = [0] * (n+1)
def dfs(u): # 表示枚举到第几位
    if u > n:
        for i in range(1,n+1):
            print(st[i],end = ' ')
        print()
        return
    for i in range(1,n+1): # 依次枚举每个分支，即当前位置可以填哪些数
        if not used[i]:
            st[u] = i
            used[i] = 1
            dfs(u+1)
            st[u] = 0
            used[i] = 0
dfs(1)

递归实现组合型枚举:

思路:要求当前位置的下一位的位置不能小于当前位置

n,m = map(int,input().split())
st = [0] * 30
def dfs(u,start): # u 表示第几位(正在选第几位，已经选了u-1位),start表示从哪开始
    if u + n - start < m: # u - 1 + n - start + 1 < m 剪枝
        return 
    if u > m:
        for i in range(1,m+1):
            print(st[i],end = ' ')
        print()
        return
    for i in range(start,n+1):
        st[u] = i
        dfs(u+1,i+1)
        st[u] = 0
dfs(1,1)