如何用itertools解决无序排列组合的问题

最近我作为Python菜鸟一枚开始征战Codewars，所以打算在这里记下遇到的有意思的题目。今天这第一题叫做“Best Travel”：

John和Mary计划去一些小镇旅行。Mary已经列好了这些小镇之间的距离比如ls=[50, 55, 57, 58, 60]。但是John不想开车太累，所以提出了两个要求：1) 开车不超过某个距离比如t=174 miles 2) 只能去3个小镇。

选择哪3个小镇可以让John和Mary都满意呢？（即找到距离之和最接近或等于t的3个小镇）

这道题目可以抽象成：

输入一个整数列表ls和整数t：

1. 找出从ls中任取三个元素的所有组合

2. 计算每个组合的三个元素之和

3. 如果存在小于或等于t的和，那么从中挑出最大的，然后输出这个最大和对应的三元素组合

4. 如果不存在，只好返回None

实现要点：

1. 无序排列组合：

用itertools模块的combinations方法

2. 求和：

用sum函数

3. 求最大值：

用max函数

4. 捕获异常：

用try-except

借用这一题的某个best solution, 实现代码为：

def choose_best_sum(t, k, ls):
  import itertools

  try:
    return max(sum(combination) for combination in itertools.combinations(ls, k) if sum(combination) <= t)
  except:
    return None

以上这篇如何用itertools解决无序排列组合的问题就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python 排列组合之itertools

    python 2.6 引入了itertools模块,使得排列组合的实现非常简单: 复制代码 代码如下: import itertools 有序排列:e.g., 4个数内选2个排列: 复制代码 代码如下: >>> print list(itertools.permutations([1,2,3,4],2))[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4,

  • 如何用itertools解决无序排列组合的问题

    最近我作为Python菜鸟一枚开始征战Codewars,所以打算在这里记下遇到的有意思的题目.今天这第一题叫做"Best Travel": John和Mary计划去一些小镇旅行.Mary已经列好了这些小镇之间的距离比如ls=[50, 55, 57, 58, 60].但是John不想开车太累,所以提出了两个要求:1) 开车不超过某个距离比如t=174 miles 2) 只能去3个小镇. 选择哪3个小镇可以让John和Mary都满意呢?(即找到距离之和最接近或等于t的3个小镇) 这道题目可

  • 如何用Java实现排列组合算法

    需求 我们的数据表有多个维度,任意多个维度组合后进行 group by 可能会产生一些"奇妙"的反应,由于不确定怎么组合,就需要将所有的组合都列出来进行尝试. 抽象一下就是从一个集合中取出任意元素,形成唯一的组合.如[a,b,c]可组合为[a].[b].[c].[ab].[bc].[ac].[abc]. 要求如下: 组合内的元素数大于 0 小于等于 数组大小: 组合内不能有重复元素,如 [aab] 是不符合要求的组合: 组合内元素的位置随意,即 [ab] 和 [ba] 视为同一种组合:

  • Python基于回溯法子集树模板解决数字组合问题实例

    Python基于回溯法子集树模板解决数字组合问题实例

    本文实例讲述了Python基于回溯法子集树模板解决数字组合问题.分享给大家供大家参考,具体如下: 问题 找出从自然数1.2.3.....n中任取r个数的所有组合. 例如,n=5,r=3的所有组合为: 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5 分析 换个角度,r=3的所有组合,相当于元素个数为3的所有子集.因此,在遍历子集树的时候,对元素个数不为3的子树剪枝即可. 注意,这里不妨使用固定长度的解. 直接套用子集树模板.

  • 解决mysql 组合AND和OR带来的问题

    如下所示: SELECT prod_name,prod_price FROM products WHERE vend_id = 1002 OR vend_id= 1003 AND prod_price >= 10; 上面这条语句 返回的结果不是我们想要的. 分析: 原因在于计算的次序.SQL 在处理OR操作符前 优先处理AND操作符.当SQK看到上述WHERE子句时,由于AND在计算次序中优先级更高,操作符被错误的组合了. 此问题的解决方法是使用圆括号明确地分组相应的操作符. 请看下面的SELE

  • c# 如何用lock解决缓存击穿

    背景 缓存击穿是指缓存中没有但数据库中有的数据(一般是缓存时间到期),这时由于并发用户特别多,同时读缓存没读到数据,又同时去数据库去取数据,引起数据库压力瞬间增大,造成过大压力. 解决方案 1.设置热点数据永远不过期. 2.加互斥锁,互斥锁参考代码如下: 2.1.根据key生成object() private static object GetMemoryCacheLockObject(string key) { string cacheLockKey = string.Format(Memor

  • C语言 如何用堆解决Topk问题

    C语言 如何用堆解决Topk问题

    目录 前言 TopK问题 解题方法 代码实现与讲解 运行结果 函数解读 PrintTopK 解读 TestTopK 解读 前言 本篇将详细讲解如何利用小根堆的方法解决TopK问题,这么多数据要处理, 该算法时间复度居然只需 TopK问题 TopK问题介绍:在N个数中找出最大的前K个 (比如在1000个数中找出最大的前10个) 解题方法 方法1:先排降序,前N个就是最大的.  时间复杂度:   方法2:N个数依次插入大堆,HeapPop K次,每次取堆顶的数据,即为前K个. 时间复杂度: 假设N非

  • 如何用Nginx解决前端跨域问题

    前言 在开发静态页面时,类似Vue的应用,我们常会调用一些接口,这些接口极可能是跨域,然后浏览器就会报cross-origin问题不给调. 最简单的解决方法,就是把浏览器设为忽略安全问题,设置--disable-web-security.不过这种方式开发PC页面到还好,如果是移动端页面就不行了. 解决办法 使用Nginx转发请求.把跨域的接口写成调本域的接口,然后将这些接口转发到真正的请求地址. 举个栗子 例如我们在开发一个Vue应用. 原先: 调试页面是: http://192.168.1.1

  • 在Python中使用itertools模块中的组合函数的教程

    理解新概念 Python V2.2 中引入了迭代器的思想.唔,这并不十分正确:这种思想的"苗头"早已出现在较老的函数 xrange() 以及文件方法 .xreadlines() 中了.通过引入 yield 关键字,Python 2.2 在内部实现的许多方面推广了这一概念,并使编程定制迭代器变得更为简单( yield 的出现使函数转换成生成器,而生成器反过来又返回迭代器). 迭代器背后的动机有两方面.将数据作为序列处理通常是最简单的方法,而以线性顺序处理的序列通常并不需要都同时实际 存在

  • 用好Regsvr32　解决系统疑难杂症

    初识Regsvr32 想必Regsvr32大家一定都不陌生吧,在一些电脑教程或电脑杂志上总能看到它的身影,可如此一个高出镜率的 "小明星"在我们很多人的眼里却显得十分的神秘,原来一般的文章都很少对它进行介绍,最多只是了了几句介绍一下如何用它解决常见问题,好多朋友可能都已经在一些文章的指导下使用过好多次Regsvr32了,但对它的"身世"却依然不了解,今天笔者就借这篇文章打消大家脑海里的疑团,带大家一起去认识一下这个Regsvr32. Regsvr32的背景与功能 R

  • Python实现的排列组合计算操作示例

    Python实现的排列组合计算操作示例

    本文实例讲述了Python实现的排列组合计算操作.分享给大家供大家参考,具体如下: 1. 调用 scipy 计算排列组合的具体数值 >> from scipy.special import comb, perm >> perm(3, 2) 6.0 >> comb(3, 2) 3.0 2. 调用 itertools 获取排列组合的全部情况数 >> from itertools import combinations, permutations >>

随机推荐