python排列组合

这篇具有很好参考价值的文章主要介绍了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次操作:
python排列组合
步骤:
用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 ;文章来源地址https://www.toymoban.com/news/detail-461246.html

到了这里,关于python排列组合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数学-排列组合的理解

    排列是有顺序的排队,从 m 中选择 n 个进行排队,第 1 个有 m-0 种选择,第 2 个有 m-1 种选择,自然的,第 n 个有 m-(n-1) 种选择。因为有顺序,可以看出前面的选择,会后面影响后面的选择,所以将选择每个的可能数相乘。 A m n = ( m − 0 ) ∗ ( m − 1 ) ∗ . . . ∗ ( m − ( n − 1

    2023年04月16日
    浏览(41)
  • java实现排列组合算法

    我这里只写了组合的算法。         假设现有 M=4 个数据 a,b,c,d。从中随机抽取n个数,n为1—4个数据进行组合。那么数学中的计算组合方式为C(4,1) + C(4,2) + C(4,3) + C(4,4)  = 4 + 6 + 4 + 1 = 15。那么共有15种组合方式。 方案一:此方法容易理解但是效率慢         我的做

    2024年02月13日
    浏览(46)
  • 【SQL开发实战技巧】系列(二十三):数仓报表场景☞ 如何对数据排列组合去重以及通过如何找到包含最大值和最小值的记录这个问题再次用执行计划给你证明分析函数性能不一定高

    【SQL开发实战技巧】系列(一):关于SQL不得不说的那些事 【SQL开发实战技巧】系列(二):简单单表查询 【SQL开发实战技巧】系列(三):SQL排序的那些事 【SQL开发实战技巧】系列(四):从执行计划讨论UNION ALL与空字符串UNION与OR的使用注意事项 【SQL开发实战技巧】系列

    2023年04月10日
    浏览(67)
  • 【算法教程】排列与组合的实现

    在讲排列与组合之前,我们先定义数据元素类型Fruit 对N个不同元素进行排序,总共有多少不同的排列方式? 例子:某水果店有以下水果,请对所有水果进行全排列,请输出所有排列 排列算法的javascript实现模板(DSF,最优解in-place) 测试结果 对N个不同元素进行排序,总共有多少不

    2024年02月07日
    浏览(42)
  • 【马蹄集】—— 概率论专题:排列组合

    难度:黄金    时间限制:1秒    占用内存:128M 题目描述 小码哥正在进行抽奖,箱子里有一红一白两小球,每次摸出一个球,摸到红球中奖, 如果中奖,就不再继续抽奖;如果未中奖 (摸到白球),则往箱子里补充一个白球 (摸出的白球不放回),继续抽奖,直到中奖,或

    2024年02月07日
    浏览(37)
  • 递归实现 组合问题+排列问题(DFS)

    目录 递归实现排列型枚举 递归实现排列类型枚举 II  递归实现组合型枚举 递归实现组合型枚举 II 递归实现指数型枚举 递归实现指数型枚举 II 递归不是循环,递归利用了系统栈,只要是函数都会被系统管理。当执行到函数地址入口时就会为函数在系统栈上分配一块内存。当

    2024年02月15日
    浏览(44)
  • STL—next_permutation函数

    目录 1.next_permutation函数的定义 2.简单使用 2.1普通数组全排列  2.2结构体全排列 2.3string 3.补充 next_permutation函数 会按照字母表顺序生成给定序列的 下一个较大的排列 ,直到整个序列为 降序 为止。与其相对的还有一个函数—— prev_permutation函数。 next_permutaion(起始地址,末尾

    2024年02月04日
    浏览(86)
  • 排列(Amn)与组合(Cmn)算法详解

    不区分个体差异和顺序时用Cmn(m小n大),需要区分个体和顺序时候用Amn。 例1:从10个相同的球里取出5个球,不需要区分先后顺序,也不区分其他个体特征,一把抓过去够5个就行,这就是C510(m=5,n=10)。 例2:有10把凳子,需要安排10个人去坐,问有多少种可能性。这里,就需要体

    2024年02月04日
    浏览(39)
  • 【C++】 排列与组合算法详解(进阶篇)

    写在前面 我上次发了一篇题解:C++排列与组合算法详解 最开始,我是抱着水题解的想法写的,但却成为了阅读量 最高 的文章,没有之一。 所以今天咱们来重制一篇文章,介绍几个进阶优化版的算法。 算法1:朴素算法 思路 具体见 C++排列与组合算法详解 缺点 不能将结果取

    2024年02月13日
    浏览(39)
  • PostgreSQL里实现计算多个数字的排列组合

    在进行排列组合的时候,每一次需要知道是否有重复的值,并过滤出已经排列过的值。这个可以创建支持可变参数的函数来实现。下边的函数用到了聚合判断,并且可变参数使用variadic标记的数组。 然后是如何使用这个函数结合查询语句对一组数据进行排列组合。 先创建一个

    2024年02月21日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包