算法第二期——排列组合（Python）;

发布人：shili8 发布时间：2023-03-22 16:48 阅读次数：18

排列函数permutations( )

易错点

组合函数combinations( )

手写排列和组合代码

1.暴力法

（1）排列

（2）组合

2.二进制法

（1）组合

问题1：输出n个数的任意组合（所有子集）

问题2：输出n个数的任意m个数的组合

例题：排列序数

例题：拼数

例题：火星人

例题：带分数

排列函数permutations( )

itertools.permutations(iterable,r = None)
功能：连续返回由 iterable序列中的元素生成的长度为r的排列。
如果r未指定或为None，r默认设置为 iterable 的长度即生成包含所有元素的全排列 (n!个)

from itertools import *
s = ['a','b','c']
for element in permutations(s, 2): # 每次从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 acb cba cab”，按位置表示就是“123 132 213 231 312 321”，这是按从小到大的顺序输出的.

from itertools import *
s = ['b','a','c']
for element in permutations(s):
    a="".join(element)
    print(a,end=' ') # bac bca abc acb cba cab

如果有相同的元素，因为在不同位置，所以被认为是不同的。例如s =[a，a，c]，执行permutations(s)，输出
aac aca aac aca caa caa

from itertools import *
s = ['a','a','c']
for element in permutations(s):
    a="".join(element)
    print(a,end=' ') # aac aca aac aca caa caa

易错点

初学者容易犯一个错误，把元素当成了位置。
例如s =['1','3','2']，执行permutations(s)，输出“132 123 312 321 213 231”
看起来很乱，实际上是按3个元素的位置'1'=1、'3'=2、'2'=3输出有序的排列的。

from itertools import *
s = ['1','3','2']
for element in permutations(s):
    a="".join(element)
    print(a,end=' ') # 132 123 312 321 213 231

# 数字不能直接用join
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()排序为['1'，'2'，'3']，再执行permutations()

from itertools import *
s = ['1','3','2']
s.sort()
for element in permutations(s):
    a =''.join(element)
    print(a,end=' ') # 123 132 213 231 312 321

不拼接直接输出，输出结果是元组的形式

from itertools import *
s = ['1','3','2']
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')

组合函数combinations( )

permutations( )输出的是排列，元素的排列是分先后的，“123”和“321”不同
有时只需要输出组合，不用分先后，此时可以用combinations( )函数

from itertools import *
s = ['1','3','2']
for element in combinations(s,2):
    a = ''.join(element)
    print(a,end=' ') # 13 12 32

注意

如果序列s中有相等的元素，那么不同位置的相等元素被认为不同。

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

如果要去重，用集合，s用{ }表示

from itertools import *
s = {'1', '1', '3', '2'} # 用集合去重
for element in combinations(s,2):
    a = ''.join(element)
    print(a,end=' ') # 13 12 32

此时上面输出是随机的: 23 21 31，12 13 23，13 12 32

如果要去重且输出按字典序: 先用set0去重，再排序，最后组合

from itertools import *
s = ['1', '1', '3', '2'] 
t  = list(set(s))
t.sort()
for element in combinations(t,2):
    a = ''.join(element)
    print(a,end=' ') # 12 13 23  结果唯一

from itertools import *
s = ['1', '1', '3', '2'] 
t  = sorted(set(s))
for element in combinations(t,2):
    a = ''.join(element)
    print(a,end=' ') # 12 13 23  结果唯一

手写排列和组合代码

在某些场景下，系统排列函数并不能用，需要手写代码实现排列组合
在“DFS与排列组合”中给出了基于DFS的手写方法。

下面给出几种简单的手写方法：

1.暴力法

（1）排列

从{1,2,3,4}中选3个的排列，有24种。
最简单直接无技巧的手写排列:

s =[1,2,3,4]
for i in range(4):
    for j in range(4):  #循环3次，选3个数。
        if j !=i: # #每个循环的数不同
            for k in range(4):
                if k !=j and k!=i: #每个循环的数不同
                    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，

【优缺点】简单且效果很好，但是非常笨拙。如果写5个以上的数的排列组合，代码冗长无趣。

（2）组合

排列数需要分先后，组合数不分先后。

把求排列的代码，去掉if，然后从小到大打印即可

从{1,2,3,4}中选3个的组合，有4种。

s =[1,2,3,4]
for i in range(4):
    for j in range(i+1,4):  #循环3次，选3个数。
            for k in range(j+1,4):
                    print("%d%d%d"%(s[i],s[j],s[k]),end="，") # 123，124，134，234，

2.二进制法

（1）组合

一个包含n个元素的集合{a0,a1,a2,a3,., an-1}，它的子集有{ $\varphi$ }，{ $a_{0}$ }，{ $a_{1}$ }，{ $a_{2}$ },..…, { $a_{0}$ , $a_{1}$ , $a_{2}$ ),...…,{ $a_{0}$ , $a_{1}$ , $a_{2}$ , $a_{3}$ ,..., $a_{n-1}$ }，共 $2^{n}$ 个。

每个子集对应了一个二进制数。二进制数中的每个1，对应了子集中的某个元素。
子集中的元素，是不分先后的，这正符合组合的要求。例如： $a_{0}$ , $a_{1}$ , $a_{2}$ 和 $a_{2}$ , $a_{0}$ , $a_{1}$ 是一样的。

问题1：输出n个数的任意组合（所有子集）

下面的代码通过处理每个二进制数中的1，打印出了所有的子集

a =[1,2,3,4,5,6]
n=3                        # #打印前n个元素a[o]~a[n-1]的所有子集
for i in range(1<<n):      # 打印所有子集出现的可能结果
# 打印前n个元素就左移n位，子集为2的n次方
    print('{',end='')      
    for j in range(n):     #打印一个子集
        if i & (1<<j):     #从二进制的最低位开始，逐个比较i,j每一位，都是1则为1，打印十进制结果
            print(a[j],end='，')   # 打印满足要求的i中1的位置
    print('}',end=";")
# {};{1，};{2，};{1，2，};{3，};{1，3，};{2，3，};{1，2，3，};

其中：

1<<n	若n=2，1的二进制为 0000 0001 左移2位 0000 0100. 转成10进制就是4。
&	按位与运算符：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0

举个例子：

a = 60            # 60 = 0011 1100
b = 13            # 13 = 0000 1101
c = a & b         # 12 = 0000 1100
print(c) # 12

问题2：输出n个数的任意m个数的组合

根据上面子集生成的二进制方法，一个子集对应一个二进制数;一个有m个元素的子集，它对应的二进制数中有m个1。
所以问题转化为: 查找1的个数为m个的二进制数，这些二进制数对应了需要打印的子集。
如何判断二进制数中1的个数为m个简单的方法是对这个n位的二进制数逐位检查，共需要检查n次

举个栗子：输出3个数的任意2个数的组合。在000~111中找，两个数的组合只有三种：011,101,110。

如何判断二进制数中1的个数为m个

简单的方法是对这个n位的二进制数逐位检查，每个子集共需要检查n次，但如果位数太多，查找起来比较费力。。。
有一个更快的方法，可以直接定位二进制数中1的位置，跳过中间的0。(每个子集最多检查m次）

第二个方法用到一个神奇操作:k=k&(k-1)，功能是消除k的二进制数的最后一个1。连续进行这个操作，每次消除一个1，直到全部消除，操作次数就是1的个数。例如二进制数1011，经过连续3次操作后，所有1都消除了:

1011 &(1011-1)=1011 & 1010=1010
1010&(1010-1)=1010 &1001 =1000
1000 &(1000-1)=1000&0111 = 0000

· 利用这个操作，可以计算出二进制数中1的个数。用num统计1的个数。

步骤：

用k =k&(k-1)清除k的最后一个1:
num++:
继续上述操作，直到k=0。

a = [1, 2, 3, 4, 5, 6, 7]
def print_set(n, m):
    for i in range(2 ** n):  # 2**n可以写成1<<ni
        num, k = 0, i        # num=0:初始化+清零,num统计i中1的个数;k用来处理
        while k > 0:
            k = k & (k - 1)  # 清除k中最后一个1
            num += 1         # i中1的个数就加1
            if num > m:      # 子集的二进制数中的1超过m个就不用统计了
                break
        if num == m:         # 子集中二进制数中的1有m个才符合条件
            for j in range(n): # 打印出满足要求的i中1所在的位置
                if i & (2 ** j):
                    print(a[j], end=' ')
            print("; ", end="")
n, m = 4, 3                  # 取4位二进制数的前3位
print_set(n, m)  # 1 2 3 ; 1 2 4 ; 1 3 4 ; 2 3 4 ;

还是看不懂可以看我下面这个解释：（下面这个图是当时给别人解答的时候写的）

例题：排列序数

题目补充：如果把它们排个序，每个串都对应一个序号：abcd 0,abdc 1,acbd 2,acdb 3,adbc 4,adcb 5,bacd 6,badc 7,bcad 8,bcda 9,bdac 10,bdca 11,cabd 12,cadb 13,cbad 14,cbda 15,cdab 16,cdba 17, 以此类推。

思路：

可以发现上面的排序是按照abcd（字典序）的位置顺序来输出的。

下面给出两种代码，分别用sort()和sorted()排序将字符串变成字典序，然后用permutions()求位置顺序的排列。

1) 用sort()函数。sort()不能直接在字符串内部排序。可以这样:把字符串转换成list（因为sort函数是list特有的），对数组排序后，再转换回字符串，就得到了最小字符串。

from itertools import *
olds = input()              # 目标排列   例: olds = bdca   
news = list(olds)           # 把字符串olds转换成数组news
news.sort()                 # 对数组排序。例:news =[a，b，c，d]
cnt =0        # 序号
for element in permutations(news):
    a = "".join(element)      # 把所有元素拼回成字符串
    if olds == a:           # 找到olds就输出它的序号
        print(cnt)
        break
    cnt += 1                # 不是olds，序号就加一

2) 用sorted0函数。sorted0能直接在字符串的内部排序。

注意如果题目有十个字母，第6行生成的a中包含10!个排列，可能导致超出题目的空间限制。

from itertools import *
olds = input()              # 例: olds =bdca
news = sorted(olds)         # 例: news =['a','b','c'，'d']
a = []
for i in permutations(news):
    a.append(i)
print(a.index(tuple(olds)))  # 注意这里是olds

例题：拼数

【简单粗暴法】：先得到这n个整数的所有排列，然后找其中最大的。但是这个方法的复杂度是O(n!)，当n=20时，有20!= 2X $10^{18}$ 种排列，超时。。。

from itertools import *
N = int(input())                        # 其实没用到
ans = ''
nums =list( map(str,input().split()))   # 按字符的形式读入
for element in permutations(nums):      # 每次输出一个全排列
    a="".join(element)                  # 把这个全排列的所有元素拼起来，得到一个串
    if ans < a:                         # 在所有串中找最大的
        ans = a                         # 如果有比ans更大的，将这个数赋值给ans
print(ans)

【推荐做法】：暴力排列不行，可以用排序吗本题不能直接对数字排序然后首尾相接，例如“7，13”，应该输出“713”而不是“137”。注意到这其实是按两个数字组合的字典序(先比较第一位数，再逐一比较后面的数)排序，也就是把数字看成字符串来排序。本题的n很小，用较差的排序算法也行，例如交换排序。第3-6行用交换排序对所有的数(按字符串处理) 进行排序，复杂度O( $n^{2}$ )。

n = int(input())
nums = input().split()                         # 按字符读入
for i in range(0,n-1):                         # 交换排序
    for j in range(i+1,n):
        if nums[j]+nums[i]>nums[i]+nums[j]:    #字符串合并然后比较
            nums[j],nums[i] = nums[i],nums[j]  #交换两个数(其实是字符串)的位置
print("".join(nums))

注意：字符串‘数字’比较大小比较的是字典序大小！

例题：火星人

用Python编码比较麻烦，因为Python的permutations()函数是按元素位置进行排列的输出的,只能这样编码:先把n个数排序成最小排列，然后从这个最小排列开始permutations()，遇到题目给定的起始排列后，再往后数到第m个排列，输出。但是这个代码会超时，因为浪费了很多计算。

from itertools import *
from copy import *
n = int(input())
m = int(input())
nums = list( map(str,input().split()))
back = deepcopy(nums) # 深度拷贝生成新的list。不能写back = nums，这是浅拷贝
# 浅拷贝：修改其中一个，另一个也会改变
# 不用deepcopy也可以用for循环将nums存到back
k=0   # 统计排列次序
flag = 0
nums.sort() #排序，得到最小排列
for element in permutations(nums): #每次输出一个全排列，这样会超时
    if list(element) == back: #循环到了题目给的起始排列
        flag= 1
    if flag == 1:            # 找到了起始排列才开始计数：k += 1
        if k == m:
            a=''.join(element) #把这个全排列的所有元素拼起来，得到一个串
            print(a)            #输出后面第k个排列
            break               #退出for循环
        k += 1

【推荐做法】：手写寻找下一个排列：从当前排列开始，暴力地寻找下一个排列。对于当前排列，从后往前比较，寻找nums[i-1]<nums[i]的位置（第一个不是递增的位置），把nums [i-1]与i到末尾中比nums[i-1]大的最小数（从后往前找，第一个满足比num[i-1]大就是最小值，因为从后往前是递增的）交换，再将i-1之后的数进行翻转 (从小到大排序)，可以得到比当前排列大的最小排列。

【图解】：

举个栗子: 如上图所示，13524—（最后两个（nums[i-1]<nums[i]）只需交换即可）—>13542——>14235（下面以红色部分进行讲解）。对于当前排列，从后往前比较，寻找nums[i-1]（3）<nums[i]（5）的位置，把nums [i-1]（3）与i（第3个）到末尾中比nums[i-1]（3）大的最小数（4）交换，再将i-1（第2个）之后的数（532）进行翻转 （235）(从小到大排序)，可以得到比当前排列大的最小排列（14235）。

n = int(input())
m = int(input())
nums = list(map(int, input().split()))
def find_next(nums):                           # 求下一个排列
    for i in range(n - 1, 0, -1):              # 从后往前寻找前面小于后面的相邻数
        if nums[i] > nums[i - 1]:
            for j in range(n - 1, i - 1, -1):  # 从后往前找比num[i-1]大的最小值：第一个满足比num[i-1]大就是最小值，因为从后往前是递增的
                if nums[j] > nums[i - 1]:
                    nums[j], nums[i - 1] = nums[i - 1], nums[j]  # 交换
                    return nums[:i] + nums[:i - 1:-1]  #再将i-1之后的数（从i开始）进行翻转 

for i in range(m):      # #找后面第m个排列
    nums = find_next(nums)  
print("".join([str(i) for i in nums]))

注意： nums[:i - 1:-1] ：从后到i-1反向遍历

例题：带分数

【解法1】典型的排列题。题目中说“数字1~9分别出现且只出现一次”，用暴力排列: 对所有1~9的排列，验证有几个符合要求。9个数只有9!=362880种排列，不会超时。

【解法2】

from itertools import *
n = int(input())
bit = len(str(n))                       # n的位数
cnt =0
for num in permutations("123456789"):
    a,b,c=0,0,0
    for a1 in range(bit):               # a1: a的位数，a肯定比n短
        a =int("".join(num[:a1+1]))     # 一个a
        bLast=(n -a)*int(num[-1])%10    # #运用了数学知识，取到被除数b的尾数，(n-a)c%10
        if bLast == 0:                  # b的尾数不可能等于0，因为只用到1~9
            continue
        b1 = num.index(str(bLast))      # 根据b的尾数，确定b的长度
        if b1 <= a1 or b1 >= 8:         # 防止 b_index是在a中包含和防止完全占据c的位置
            continue
        b =int("".join(num[a1+1:b1+1]))
        c =int("".join(num[b1+1:]))
        if b%c == 0 and n==a+b // c:
            cnt +=1
print(cnt)

本文参考罗勇军老师的蓝桥云课

上一条：Python 多线程

下一条：Python应用之爬虫基础：requests爬虫库的简单使用(1)

算法第二期——排列组合（Python）;

排列函数permutations( )

易错点

组合函数combinations( )

手写排列和组合代码

1.暴力法

（1）排列

（2）组合

2.二进制法

（1）组合

问题1：输出n个数的任意组合（所有子集）

问题2：输出n个数的任意m个数的组合

例题：排列序数

思路：

例题：拼数

例题：火星人

例题：带分数

免责声明