Python的排列组合调用内置函数、自写算法DFS实现
排列组合是数学中的一种常见的计算方法,用于求出从给定的元素中选取若干个元素的所有可能的排列或组合。在Python中,有多种方式可以实现排列组合的计算。
本文将介绍两种主要的方法:调用内置函数和自写算法DFS实现。
目录
调用内置函数
Python标准库中提供了一个模块itertools,该模块包含了许多用于生成迭代器的工具函数,其中就有2个函数可以用于计算排列组合,分别是:
- permutations(p [, r]):从序列p中取出r个元素的组成全排列,组合得到元组作为新迭代器的元素。
- combinations(p, r):从序列p中取出r个元素组成全组合,元素不允许重复,组合得到元组作为新迭代器的元素。
这2个函数都返回一个迭代器对象,可以使用list()函数将其转换为列表,或者使用for循环遍历其元素。下面是一个简单的例子:
对于1到n个数进行排列,使用内置函数permutations(iterable,r=None);
permutations(iterable,r=None) 连续返回iterable序列中的元素生成的长度为r的排列,如果r未指定或者为None,则默认值为iterable的长度。
-
from itertools import *
-
s = [1,2,3,4,5]
-
for element in permutations(s,2):
-
a = "".join(str(element))
-
print(a,end="")
-
out[1]:(1, 2)(1, 3)(1, 4)(1, 5)(2, 1)(2, 3)(2, 4)(2, 5)(3, 1)(3, 2)(3, 4)(3, 5)(4, 1)(4, 2)(4, 3)(4, 5)(5, 1)(5, 2)(5, 3)(5, 4)
如果需要枚举的数少的情况,可以直接通过暴力法
-
for i in range(5):
-
for j in range(5):
-
if i!=j:
-
print(s[i],s[j])
暴力法对于数字少的情况,效果好且简单。
对于1到n个数进行组合,使用内置函数combinations(iterable,r=None)
-
In [30]: from itertools import *
-
s = {1,2,3,4}
-
for element in combinations(s,3):
-
a = "".join(str(element))
-
print(a,end="")
-
(1, 2, 3)(1, 2, 4)(1, 3, 4)(2, 3, 4)
自写算法DFS实现
除了使用内置函数外,我们也可以自己编写算法来实现排列组合的计算。一种常见的算法是使用深度优先搜索(DFS)来遍历所有可能的情况,并将满足条件的结果保存下来。下面是一个使用DFS实现全排列和全组合的例子:
-
a = [1,2,3,4,5]
-
def dfs(s,t):
-
if s==2:
-
for i in range(0,2):
-
print(a[i],end="")
-
print(" ")
-
return
-
for i in range(s,t 1):
-
a[s],a[i] = a[i],a[s]
-
dfs(s 1,t)
-
a[s],a[i] = a[i],a[s]
-
dfs(0,4)
上述代码虽然很短,但有个缺点就是不能从小到大输出排列。
改进之后的代码:实现从小到大输出
-
a = [1,2,3,4,5]
-
b = [0] * 10
-
vis = [0] * 20
-
def dfs(s,t):
-
if s==2:
-
for i in range(0,2):
-
print(b[i],end="")
-
print(" ")
-
return
-
for i in range(0,t):
-
if not vis[i]:
-
vis[i] = True
-
b[s] = a[i]
-
dfs(s 1,t)
-
vis[i] = False
-
dfs(0,5)
自写算法实现组合:
-
# 首先,我们定义一个函数dfs,它接受五个参数:
-
# - cur: 当前遍历到的元素的下标,初始为0
-
# - m: 要选出的元素个数
-
# - cur_list: 保存当前已选出的元素的列表
-
# - original_list: 给定的n个元素的列表
-
# - result_list: 保存最终结果的列表
-
-
def dfs(cur, m, cur_list, original_list, result_list):
-
# 如果已经选出了m个元素,就把当前列表添加到结果列表中,并返回
-
if m == 0:
-
result_list.append(list(cur_list))
-
return
-
# 如果还没有选出m个元素,就从当前下标开始,遍历原始列表中的每个元素
-
for i in range(cur, len(original_list)):
-
# 把当前元素添加到当前列表中
-
cur_list.append(original_list[i])
-
# 递归地调用dfs函数,更新下标和剩余元素个数
-
dfs(i 1, m - 1, cur_list, original_list, result_list)
-
# 回溯时,把当前元素从当前列表中移除
-
cur_list.pop()
-
-
# 然后,我们定义一个测试函数,给定一个原始列表和一个目标个数,调用dfs函数,并打印结果列表
-
-
def test(original_list, m):
-
# 初始化结果列表为空列表
-
result_list = []
-
# 调用dfs函数,传入初始下标为0,空的当前列表和结果列表
-
dfs(0, m, [], original_list, result_list)
-
# 打印结果列表
-
print(result_list)
-
-
# 最后,我们用一个例子来测试一下我们的算法,假设原始列表为[1, 2, 3, 4],目标个数为2
-
-
test([1, 2, 3, 4], 3)
-
-
# 输出结果为:
-
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
-
-
# 可以看到,我们的算法成功地找到了所有的组合,并用DFS的方式遍历了它们。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfeaag
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01