排列组合问题在是算法中很基础的一个问题,它们的区别就是,排列要考虑顺序,组合不考虑顺序。在面试的过程中可能会考到,在现实生活中也是经常可以遇到的,比如说一个3位数字的密码锁,要尝试多少次才能解开?那么用python有哪些方法可以解决此类问题呢?
以一个具体的例子来说明在python中此类问题的可能解决方法,要求给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
- num_list = [1,2,3]
- result = []
- for i in num_list:
- for j in num_list:
- for k in num_list:
- if len(set((i,j,k))) == 3:#去重后长度仍为3的话说明i,j,k的值都不相同
- result.append(list((i,j,k)))
- print(result)
输出结果:
说明:for循环遍历是很容易想到的方法,但是如果列表中的元素比较多的时候那么嵌套的for循环就会很多,写起来很麻烦。
python有现成的处理排列组合的模块叫itertools,可以借助其来实现。需要先import itertools将其导入,查看其中的方法:
函数语法:
permutations(iterable[, r]) --> permutations object
输入两个参数分别为:可迭代对象,从可迭代对象中取出几个值来计算其排列
代码示例:
- #encoding =utf-8
- num_list = [1,2,3]
- def permute(nums):
- from itertools import permutations
- result = []
- for i in permutations(nums,len(nums)):
- result.append(list(i))
- return result
- print('\n')
- print(permute(num_list))
输出结果:
说明:自带的模块确实很强大,对于列表的长度没有限制,可随意生成任意的排列组合
eval()将字符串当作有效的python表达式来执行,测试框架中拼指令的时候用的很多。
- import string
- num_list = [1,2,3]
- length = len(num_list)
- var = tuple([string.ascii_lowercase[i] for i in range(length)])#生成字母代表的变量序列
- temp = "["+','.join(var)+"]"
- result = eval("["+temp+''.join(['for %s in num_list '%i for i in ''.join(var)])+'if len(set(%s))==3'%temp+"]")
- print(result)
输出结果:
- #encoding =utf-8
- num_list = [1,2,3]
- def permute(nums):
- from functools import reduce
- result = [list(i) for i in reduce(lambda x,y:[str(a)+str(b) for a in x for b in y if str(b) not in str(a) ],[nums]*len(nums))]
- return result
- print(permute(num_list))
结果:
说明:
1.先执行[nums]*len(nums)生成一个二维列表,也就是[[1, 2, 3], [1, 2, 3], [1, 2, 3]];
2.借助reduce累计运算功能将数字转换成字符串拼接到一起,如果新取出来的数和之前的不重复就继续拼接;也就是执行[str(a)+str(b) for a in x for b in y if str(b) not in str(a) ],生成的是列表
3.最后由于生成的是字符串,转换为列表。
联系客服