排列和组合-蓝桥杯

╰半橙微兮° 2023-09-24 17:55 31阅读 0赞

# **一、排列函数permutations()** #

*  **xitertools.permutations(iterable, r = None)**

*  **功能:连续返回由 iterable序列中的元素生成的长度为r的排列。**

*  **如果r未指定或为None，r默认设置为 iterable 的长度，即生成包含所有元素的全排列。**

![99163db4eecd43bc91f31a1268355f0f.png][]

*  **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”，这是按从小到大的顺序输出的。

![04e6f30a25b14ad19f96766b2e5e53b9.png][]

*  **如果有相同的元素，不同位置的元素被认为不同。**

例如s =\[a，a，c，执行permutations(s)，输出“aac aca aac aca caa caa”。

![c39d19868f0f424e9f170b8dcb7efc27.png][]

*  **易错点**

初学者容易犯一个错误:把元素的值当成了位置。

例如s =\['1','3','2'\]，执行permutations(s)，输出“132 123 312 321 213 231”看起来很乱，实际上是按3个元素的位置'1'=1、'3'=2、'2'=3输出有序的排列的。

![22848911cf8a46b1b157f69fda0ea498.png][]

![a3f2e525c7ae443db7336a23c510629d.png][]

*  **如何输出看起来正常的“123 132 213 231 312 321”?**

答：先把s =\['1','3','2'\]用sort()排序为\[1,2,3\]再执行permutations()。

![7092a2363cee4dcdaaa6719bd4f9b736.png][]

*  **练习**

![89709a6f4efc4f509de5df23f37365fd.png][]

![cb263b86bbb841c9941297f2f7b2de31.png][]

# **二、组合函数combinations()** #

*  **permutations()输出的是排列，元素的排列是分先后的，“123”和“321”不同。**

*  **有时只需要输出组合，不用分先后，此时可以用combinations()函数。**

![68f390bdf182467c9165dc9645fcdc16.png][]

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

![c9032e950bb74b88a42d395ad6f969ae.png][]

*  **如果要去重怎么办?用集合，s用****集合****\{\}表示。**

![ce61f4e6b2c544dda18570a988e8f8ae.png][]

*  **当用****集合****来表示的时候，输出的组合结果的顺序是****随机****的。**

![988da351fa494636b216137d52fd50c3.png][]

*  **如果要去重且输出按字典序，就先用set()去重，再排序，最后组合。**

![1cd2f471b0b74495853fa0c90908bc7e.png][]

![396fdeff3dfd4a6ab6c8d6c32a5295af.png][]

# **三、手写排列和组合代码** #

*  **在某些场景下，Python提供的排列函数并不能用，需要手写代码实现排列组合。**

*  **在“DFS与排列组合”中给出了基于DFS的手写方法。**

*  **此时还没学到“DFS”，因此下面给出几种简单的手写方法。**

--------------------

*  **手写排列代码**

**从\{1,2,3,4\}中选3个的排列，有24种。**

**最简单直接无技巧的手写排如下。**

![33c2c230f899495499e6b8fc93a00469.png][]

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

--------------------

*  **手写组合代码**

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

**把求组合的代码，去掉if，然后从小到大打印即可。**

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

![9e387578f712400eb922c84d8e3f53c1.png][]

--------------------

*  **二进制法手写组合代码**

**一个包含n个元素的集合\{a0,a1,a2,a3,..., an-1\}，它的子集有\{空\},\{a0\},\{a1\},\{a2\},..., \{a0,a1,a2\},...,\{a0,a1,a2,a3,...,an-1\}，共2的n次方个。**

**用二进制的概念进行对照，子集正好对应了二进制。 例如n =3的集合\{a0,a1,a2\}，它的子集和二进制数的对应关系是:**

![ddec75e477e24ea590653906780f8d00.png][]

**每个子集对应了一个二进制数。二进制数中的每个1，对应了子集中的某个元素。**

**子集中的元素，是不分先后的，这正符合组合的要求。**

--------------------

**实例1操作如下：**

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

![c3ef01e8e6ec428985d0f49098a61efa.png][]

--------------------

**实例2操作如下：**

**输出n个数中任意****m个数****的组合。**

**根据上面子集生成的二进制方法，一个子集对应一个二进制数;一个有m个元素的子集，它对应的二进制数中有m个1。**

**问题转化为:****查找1的个数为m个的二进制数****，这些二进制数对应了需要打印的子集。**

**如何判断二进制数中1的个数为m个?简单的方法是对这个n位的二进制数逐位检查，共需要检查n次。**

**有一个更快的方法，可以直接定位二进制数中1的位置，跳过中间的0。用到一个神奇操作:k=k&(k-1)，功能是消除k的二进制数的最后一个1。连续进行这个操作，每次消除一个1，直到全部消除，操作次数就是1的个数。例如二进制数1011，经过连续3次操作后，所有1都消除了:**

![affcc85bfd854546a782b48bf5833974.png][]

**利用这个操作，可以计算出二进制数中1的个数。步骤:**

**1)用k=k &(k-1)清除k的最后一个1;**

**2)num++用num统计1的个数；**

**3) 继续上述操作，直到k =0。**

**输出按字典序输出，从小到大。**

![de7319da5d614ea6abd98147d82e21b8.png][]

[99163db4eecd43bc91f31a1268355f0f.png]: https://img-blog.csdnimg.cn/img_convert/99163db4eecd43bc91f31a1268355f0f.png
[04e6f30a25b14ad19f96766b2e5e53b9.png]: https://img-blog.csdnimg.cn/img_convert/04e6f30a25b14ad19f96766b2e5e53b9.png
[c39d19868f0f424e9f170b8dcb7efc27.png]: https://img-blog.csdnimg.cn/img_convert/c39d19868f0f424e9f170b8dcb7efc27.png
[22848911cf8a46b1b157f69fda0ea498.png]: https://img-blog.csdnimg.cn/img_convert/22848911cf8a46b1b157f69fda0ea498.png
[a3f2e525c7ae443db7336a23c510629d.png]: https://img-blog.csdnimg.cn/img_convert/a3f2e525c7ae443db7336a23c510629d.png
[7092a2363cee4dcdaaa6719bd4f9b736.png]: https://img-blog.csdnimg.cn/img_convert/7092a2363cee4dcdaaa6719bd4f9b736.png
[89709a6f4efc4f509de5df23f37365fd.png]: https://img-blog.csdnimg.cn/img_convert/89709a6f4efc4f509de5df23f37365fd.png
[cb263b86bbb841c9941297f2f7b2de31.png]: https://img-blog.csdnimg.cn/img_convert/cb263b86bbb841c9941297f2f7b2de31.png
[68f390bdf182467c9165dc9645fcdc16.png]: https://img-blog.csdnimg.cn/img_convert/68f390bdf182467c9165dc9645fcdc16.png
[c9032e950bb74b88a42d395ad6f969ae.png]: https://img-blog.csdnimg.cn/img_convert/c9032e950bb74b88a42d395ad6f969ae.png
[ce61f4e6b2c544dda18570a988e8f8ae.png]: https://img-blog.csdnimg.cn/img_convert/ce61f4e6b2c544dda18570a988e8f8ae.png
[988da351fa494636b216137d52fd50c3.png]: https://img-blog.csdnimg.cn/img_convert/988da351fa494636b216137d52fd50c3.png
[1cd2f471b0b74495853fa0c90908bc7e.png]: https://img-blog.csdnimg.cn/img_convert/1cd2f471b0b74495853fa0c90908bc7e.png
[396fdeff3dfd4a6ab6c8d6c32a5295af.png]: https://img-blog.csdnimg.cn/img_convert/396fdeff3dfd4a6ab6c8d6c32a5295af.png
[33c2c230f899495499e6b8fc93a00469.png]: https://img-blog.csdnimg.cn/img_convert/33c2c230f899495499e6b8fc93a00469.png
[9e387578f712400eb922c84d8e3f53c1.png]: https://img-blog.csdnimg.cn/img_convert/9e387578f712400eb922c84d8e3f53c1.png
[ddec75e477e24ea590653906780f8d00.png]: https://img-blog.csdnimg.cn/img_convert/ddec75e477e24ea590653906780f8d00.png
[c3ef01e8e6ec428985d0f49098a61efa.png]: https://img-blog.csdnimg.cn/img_convert/c3ef01e8e6ec428985d0f49098a61efa.png
[affcc85bfd854546a782b48bf5833974.png]: https://img-blog.csdnimg.cn/img_convert/affcc85bfd854546a782b48bf5833974.png
[de7319da5d614ea6abd98147d82e21b8.png]: https://img-blog.csdnimg.cn/img_convert/de7319da5d614ea6abd98147d82e21b8.png