python中的排列和组合

这篇具有很好参考价值的文章主要介绍了python中的排列和组合。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

python中自带的排列:

itertools.permutations(iterable,r=None)

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

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

from itertools import permutations
s = ['a','b','c']
for element in permutations(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 acd cba cad",按位置表示就是"123 132 213 231 312 321",这是按从小到大的顺序输出的。

python中自带的组合:

组合函数与排列函数相似,但是元素无序

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

       由于自带的排列和组合效率比较低,所以我们需要进行手写排列组合,必要时进行剪枝等操作,进行优化。

 手写排列和组合:

dfs参数有两种:一种是全局变量,另一种是形参

递归问题要手动画一个递归搜索树,有利于加深理解。

递归实现指数型枚举:

python中的排列和组合

思路: 按顺序从1~n依次考虑每个数选与不选

n = int(input())
st = [0] * 16 # st 记录每一位的状态,选与不选
def dfs(u): # u 表示当前第几位
    if u == n:
        for i in range(n):
            if st[i] == 1:
                print(i+1,end=" ")
        print()
        return 
    st[u] = 1
    dfs(u+1)
    st[u] = 0
    dfs(u+1)
dfs(0)

递归实现排列型枚举:

python中的排列和组合

思路1:依次枚举每个数放到哪个位置

思路2:依次枚举每个位置放哪个数

n = int(input())
st = [0] * (n+1)
used = [0] * (n+1)
def dfs(u): # 表示枚举到第几位
    if u > n:
        for i in range(1,n+1):
            print(st[i],end = ' ')
        print()
        return
    for i in range(1,n+1): # 依次枚举每个分支,即当前位置可以填哪些数
        if not used[i]:
            st[u] = i
            used[i] = 1
            dfs(u+1)
            st[u] = 0
            used[i] = 0
dfs(1)

递归实现组合型枚举:

python中的排列和组合

思路:要求当前位置的下一位的位置不能小于当前位置文章来源地址https://www.toymoban.com/news/detail-487922.html

n,m = map(int,input().split())
st = [0] * 30
def dfs(u,start): # u 表示第几位(正在选第几位,已经选了u-1位),start表示从哪开始
    if u + n - start < m: # u - 1 + n - start + 1 < m 剪枝
        return 
    if u > m:
        for i in range(1,m+1):
            print(st[i],end = ' ')
        print()
        return
    for i in range(start,n+1):
        st[u] = i
        dfs(u+1,i+1)
        st[u] = 0
dfs(1,1)

到了这里,关于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)
  • 【算法教程】排列与组合的实现

    在讲排列与组合之前,我们先定义数据元素类型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)
  • 排列(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)
  • 【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合

    📖题目描述 题目出处 :电话号码的字母组合 示例: 📖题解  这是一道典型的排列组合问题,根据输入,我们需要找到所有的组合。下面以输入字符串 digits = \\\"23\\\" 为例来讲解这道题目。 图解: 分析:  首先要知道输入的字符串 \\\"23\\\" 中的数字字符分别对应哪些字符串,其中

    2024年02月16日
    浏览(39)
  • 【福建事业单位-推理判断】06翻译推理、组合排列

    题目特征 后推前:不…不…,除非…否则不… 不不也可以顺着翻译 1.4.2后推前变形 1.除非A否则B 2必要条件(谁必不可少,谁在箭头后) 或为真的情况下,否1推1 选项代入去做,找选项里面的独生子(单独只出现一次的做代入),双胞胎可以后面代入做:先找小李 至少一个:

    2024年02月14日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包