Python实现排列组合算法
1.Python的排列函数permutations()
itertools.permutations(iterable,r=None)
功能:连续返回由iterable序列中的元素生成的长度为r的排列
如果r未指定或为None,r默认设置为iterable的长度,即生成包含所有元素的全排列
简单应用示例如下:
代码清单1-1:
from itertools import *
s=['a','b','c']
for element in permutations(s,2):
a=element[0]+element[1]
# 或者这样写:
# a=''.join(element) #join表示组合
print(a,end=' ')
输出:
ab ac ba bc ca cb
问:permutations()按什么顺序输出序列?
答:按元素的位置顺序输出元素的排列,也就是说,输出排列的顺序是位置的字典序。
例如s=[‘b’,‘a’,‘c’],执行permutations(s),输出“bac bca abc acb cba cab”,并不是按字符的字典序输出排列,而是按位置顺序输出。
如果有相同的元素,不同位置的元素被认为不同。例如s=[‘a’,‘a’,‘c’],执行permutations(s),输出“aac aca aac aca caa caa ”
代码清单1-2:
from itertools import *
s=['a','a','c']
for element in permutations(s):
a=''.join(element)
print(a,end=' ')
join方法只适用于字符型,数字可以采用for遍历的方法实现组合
代码清单1-3:
from itertools import *
s=[1,3,2]
for element in permutations(s):
for j in element:
print(j,end='')
print(' ',end='')
输出:
132 123 312 321 213 231
问:如何输出看起来正常的“123 132 213 231 312 321”?
答:先把s=[‘1’,‘3’,‘2’]用sort()排序之后再执行permutations()
代码清单1-4:
from itertools import *
s=[1,3,2]
s.sort()
for i in permutations(s):
print(i,end='')
输出:
(1, 2, 3)(1, 3, 2)(2, 1, 3)(2, 3, 1)(3, 1, 2)(3, 2, 1)
2.Python的组合函数combinations()
permutations()输出的是排列,元素的排列是分先后的,但有时只需要输出组合,不用分先后,此时可以使用combinations()函数
代码清单2-1:
from itertools import *
s=['1','3','2']
for element in combinations(s,2):
a=''.join(element)
print(a,end=' ')
输出:
13 12 32
3种组合,6种排列
同样,如果序列s中有相等的元素,不同位置的相等元素被认为不同。
代码清单2-2:
from itertools import *
s=['1','1','3','2']
for element in combinations(s,2):
a=''.join(element)
print(a,end=' ')
输出:
11 13 12 13 12 32
会发现重复打印“12”和“13”,想要解决问题可以用集合进行去重
代码清单2-3:
from itertools import *
s= {'1', '1', '3', '2'}
for element in combinations(s,2):
a=''.join(element)
print(a,end=' ')
输出:
12 13 23
但如果用集合表示,输出顺序是随机的,多次执行代码1-7,会发现每次输出的顺序不同
如果要去重且输出按字典序:先用set()去重,再排序,最后组合
代码清单2-4:
from itertools import *
s= {'1', '1', '3', '2'}
t=list(set(s))
t.sort() #sort排序只对list
for element in combinations(t,2):
a=''.join(element)
print(a,end=' ')
或
from itertools import *
s= {'1', '1', '3', '2'}
t=sorted(set(s)) #sorted排序不需要转换为list
for element in combinations(t,2):
a=''.join(element)
print(a,end=' ')
输出:
12 13 23
3.手写排列和组合代码
在某些场景下,Python提供的排列函数并不能用,需要手写代码实现排列组合。
下面是几种简单的手写方法:
手写排列代码:暴力法
代码清单3-1:
s=[1,2,3,4]
for i in range(4): #循环三次,选三个数
for j in range(4):
if j!=i: #保证每个循环的数不同
for k in range(4):
if k!=i and k!=j:
print("%d%d%d"%(s[i],s[j],s[k]),end=',')
输出:
123,124,132,134,142,143,213,214,231,234,241,243,312,314,321,324,341,342,412,413,421,423,431,432,
简单且效果好,但非常笨拙
手写组合代码:暴力法
代码清单3-2:
s=[1,2,3,4]
for i in range(4): #循环三次,选三个数
for j in range(i+1,4):
for k in range(j+1,4): #让第二个数比第一个大,第三个数比第二个大
print("%d%d%d"%(s[i],s[j],s[k]),end=',')
输出:
123,124,134,234,
排列数需要分先后,组合数不分先后,直接去掉if即可
手写组合代码:二进制法
一个包含n个元素的集合有2**n个子集,可以对应到二进制的概念,某一个集合中“有”或者“没有”这个元素,可以对应“1”或“0”
并且子集中的元素是不分先后的,这正符合组合的要求
下面的代码通过处理每个二进制数中的1,打印出 所有 的子集
代码清单3-3:
a=[1,2,3,4,5,6]
n=3 #打印前n个元素a[0]~a[n-1]的所有子集
for i in range(1<<n): #1左位移3,相当于2**3
#i是选取000~111的8个数
print('{',end='')
#打印一个子集,即打印i的二进制数中的所有的1
for j in range(n): #检查n次
if i & (1<<j): #从i的最低位开始,逐个检查每一位,如果是1,打印
print(a[j],end=',')
print('}',end=';')
输出:
{};{1,};{2,};{1,2,};{3,};{1,3,};{2,3,};{1,2,3,};
那么如何输出n个数中任意m个数的组合?
根据上面子集生成的二进制方法,一个子集对应一个二进制数;一个有m个元素的子集,对应的二进制数中有m个1
问题转化为:查找1的个数为m个的二进制数,这些二进制数对应了需要打印的子集
方法:可以直接定位二进制数中1的位置,跳过中间的0
用到一个神奇操作:k=k&(k-1),功能是消除k的二进制数的最后一个1,连续进行这个操作,每次消除一个1,直到全部消除,操作次数就是1的个数
例如1011只需3次操作:
步骤:
用k=k&(k-1)清除k的最后一个1;
num++ 用num统计1的个数
继续上述操作,直到k=0
代码清单3-4:
a=[1,2,3,4,5,6,7]
def print_set(n,m): #在n个数中取m个数的组合
for i in range(2**n): #2**n可以写成1<<n
num,k = 0,i #num统计i中1的个数;k用来处理i
while(k>0): #循环处理
k=k&(k-1) #清除k中最后一个1
num +=1 #统计1的个数
if num == m: #二进制数中的1有m个,符合条件
for j in range(n):
if (i&(2**j)):print(a[j],end=' ')
print("; ",end='')
n,m=4,3 #a的前4个数中选3个组合
print_set(n,m)
输出:
1 2 3 ; 1 2 4 ; 1 3 4 ; 2 3 4 ;