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)
递归实现组合型枚举:
文章来源:https://www.toymoban.com/news/detail-487922.html
思路:要求当前位置的下一位的位置不能小于当前位置文章来源地址https://www.toymoban.com/news/detail-487922.html
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)
到了这里,关于python中的排列和组合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!