专栏首页Python小屋Python版组合数计算方法优化思路和源码

Python版组合数计算方法优化思路和源码

总体说明:本文的优化思路并不局限于Python,但C、C++、C#、Java等语言无法使用内置类型直接表示大整数,需要通过数组等特定形式并自己实现大整数乘除法才能实现,因此本文只介绍Python语言的实现。

按照标准的组合数公式,再结合Python标准库的阶乘函数factorial(),很容易写出下面的代码:

def cni(n, i): from math import factorial return factorial(n) // factorial(i) // factorial(n-i)

但是,在上面代码的执行过程中,很多计算是重复的,于是我在《Python可以这样学》和《Python程序设计开发宝典》中给出了下面的优化思路和代码,大幅度减少了重复的计算,提高了计算效率。主要思路是对组合数计算公式的分子分母进行展开,并约去重复计算。

def cni1(n,i): result=1 Min,Max=sorted((i, n-i)) for i in range(n,0,-1): if i> Max: result *=i elif i <= Min: result =result // i return result

非常感谢浙江温州永嘉县教师发展中心应根球老师又对这个算法进行了进一步优化,提供了下面的两段等价代码,通过自然数分布的对称性和一乘一除的结合,有效避免了中间结果过大而导致效率降低的问题。

def cni2(n,i): result = 1 for j in range(0, i): result = result * (n-j) // (j+1) return result

def cni3(n,i): result = 1 for j in range(1, i+1): result = result * (n-i+j) // j return result

下面是测试代码,大家可以修改参数进行更多测试,也欢迎提供更好的优化思路和代码。

n = 100000 i = 52019 print(cni1(n,i)) print(cni(n,i) == cni1(n,i)==cni2(n,i)==cni3(n,i))

本文分享自微信公众号 - Python小屋(Python_xiaowu),作者:应根球,董付国

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-09-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python计算前n个自然数的阶乘和

    本文来源于粉丝私信的问题,目的在于计算result = 1!+2!+3!+...+n!,因为代码比较简单,没加注释,有问题可以留言交流。文中给出了2段代码,在实...

    Python小屋屋主
  • Python花式编程案例锦集(2)

    问题描述:编写函数,计算形式如a + aa + aaa + aaaa + ... + aaa...aaa的表达式的值,其中a为小于10的自然数。 相信大多数朋友...

    Python小屋屋主
  • Python花式编程案例锦集(1)

    首先解答上一篇文章详解Python中的序列解包(2)中最后的习题,该题答案为5,表达式功能为迭代求解序列中元素的最大值。 -----------------分割...

    Python小屋屋主
  • python列表与元组的用法

    7.列表生成式   #[i*i for i in range(10)]       [i*i for i in range(10) if i>5]

    py3study
  • <进击的虫师>如何让程序"懂很多"?

    ? 最近在做一个有意思的小项目, 在一个聊天对话中, 你向电脑提出问题, 他会自动分词,然后根据关键字, 自动答复你 对所有的关键字做出解释, 工作量实在...

    zhaoolee
  • Python计算前n个自然数的阶乘和

    本文来源于粉丝私信的问题,目的在于计算result = 1!+2!+3!+...+n!,因为代码比较简单,没加注释,有问题可以留言交流。文中给出了2段代码,在实...

    Python小屋屋主
  • 深度解读|如何构建用户分级体系实现精细化运营?附案例实操

    用户精细化分类也可以称做用户画像,是目前很常见的一种运营手段,目的是为了更好的服务不同性质的客户,提高每个环节的转化率,最大程度挖掘客户价值,创造利润。

    大数据分析不是事儿
  • 比较全的使用JavaScript获取当前网页运行环境的明细,比如操作系统类型,设备类型

    Jerry Wang
  • 资产瞎配模型(二):对瞎配(一)中净值计算错误的纠正

    上上周发的那篇资产瞎配模型,事实证明,果然是瞎配,有大佬指出组合净值计算有一定的问题,所以这里对净值计算部分及进行改正,重新计算结果。

    量化小白
  • js的深拷贝,浅拷贝

    对于字符串类型,浅复制是对值的复制,对于对象来说,浅复制是对对象地址的复制,并没 有开辟新的栈,也就是复制的结果是两个对象指向同一个地址,修改其中一个对象的属性...

    山河木马

扫码关注云+社区

领取腾讯云代金券