python解决排列组合问题的4种方式

hdzgx 2019-12-27

展开全文

前言

排列组合问题在是算法中很基础的一个问题，它们的区别就是，排列要考虑顺序，组合不考虑顺序。在面试的过程中可能会考到，在现实生活中也是经常可以遇到的，比如说一个3位数字的密码锁，要尝试多少次才能解开？那么用python有哪些方法可以解决此类问题呢？

问题

以一个具体的例子来说明在python中此类问题的可能解决方法，要求给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

方法一：for循环遍历

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循环就会很多，写起来很麻烦。

方法二：itertools模块中的permutations方法

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()

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)

输出结果：

方法四：reduce()

#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))

结果：