热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

探索高效算法:寻找所有和为N的组合方案

本文探讨了一种高效的算法,用于生成所有数字(0-9)的六位组合,允许重复使用数字,并确保这些组合的和等于给定的整数N。该算法通过优化搜索策略,显著提高了计算效率,适用于大规模数据处理和组合优化问题。

Is there a nice way for generating a list of digits (0-9), with repetitions and a length of 6, such that the sum is N, say, 20. For example:

有没有一种很好的方法来生成一个数字列表(0-9),重复和长度为6,这样总和是N,比如20。例如:

004673 -> 4+6+7+3=20
121673 -> 1+2+1+6+7+3=20
...

Thanks

4 个解决方案

#1


12  

['{0:06}'.format(i) for i in xrange(1000000) if sum(map(int,str(i))) == 20]

does the trick and needs about 5 seconds to return all 35127 numbers.

诀窍和需要大约5秒钟返回所有35127号码。

UPDATE - as a bonus, here comes the ugly-but-much-faster (~40 times faster) version:

更新 - 作为奖励,这里出现了丑陋但速度更快(约40倍)的版本:

result = []
for a in xrange(10):
    for b in xrange(10):
        for c in xrange(10):
            if a+b+c <= 20:
                for d in xrange(10):
                    if 2 

#2


6  

Much faster of other proposed solutions:

其他提出的解决方案要快得多:

def iter_fun(sum, deepness, myString, Total):
    if deepness == 0:
        if sum == Total:
            print myString
    else:    
        for i in xrange(min(10, Total - sum + 1)):
            iter_fun(sum + i,deepness - 1,myString + str(i),Total) 

def fixed_sum_digits(digits, Tot):
    iter_fun(0,digits,"",Tot) 


fixed_sum_digits(6,20)

Still some room for speeder code but then the code would be boring to be read!

仍然有一些空间用于调速器代码但是代码将无聊被阅读!

#3


2  

Using itertools and permutations:

使用itertools和permutations:

>>> from itertools import product
>>> l = []
>>> for digits in product('0123456789', repeat=6):
...     if sum(map(int, digits)) == 20:
...             l.append(digits)
...
>>> len(l)
35127
>>> l[1234]
('0', '1', '9', '0', '5', '5')

Seems to be a bit faster that eumiro's:

似乎比eumiro快一点:

>>> stm = """l = []
... for digits in product('0123456789', repeat=6):
...     if sum(map(int, digits)) == 20:
...             l.append(digits)
... """
>>> timeit.timeit(stm, setup="from itertools import product", number=3)
10.368315935134888
>>> timeit.timeit("['{0:06}'.format(i) for i in xrange(1000000) if sum(map(int,str(i))) == 20]", number=3)
14.926225900650024

#4


-1  

You can use numpy.

你可以使用numpy。

import numpy
a=[1,2,1,6,7,3]
print(numpy.cumsum(a)[-1])

推荐阅读
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 本文详细介绍了Akka中的BackoffSupervisor机制,探讨其在处理持久化失败和Actor重启时的应用。通过具体示例,展示了如何配置和使用BackoffSupervisor以实现更细粒度的异常处理。 ... [详细]
  • 本文深入探讨了 Java 中的 Serializable 接口,解释了其实现机制、用途及注意事项,帮助开发者更好地理解和使用序列化功能。 ... [详细]
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
  • 本文详细解析了Python中的os和sys模块,介绍了它们的功能、常用方法及其在实际编程中的应用。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]
  • 本文探讨了Hive中内部表和外部表的区别及其在HDFS上的路径映射,详细解释了两者的创建、加载及删除操作,并提供了查看表详细信息的方法。通过对比这两种表类型,帮助读者理解如何更好地管理和保护数据。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 主要用了2个类来实现的,话不多说,直接看运行结果,然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 2023年京东Android面试真题解析与经验分享
    本文由一位拥有6年Android开发经验的工程师撰写,详细解析了京东面试中常见的技术问题。涵盖引用传递、Handler机制、ListView优化、多线程控制及ANR处理等核心知识点。 ... [详细]
  • 本文介绍了在Windows环境下使用pydoc工具的方法,并详细解释了如何通过命令行和浏览器查看Python内置函数的文档。此外,还提供了关于raw_input和open函数的具体用法和功能说明。 ... [详细]
  • 本文深入探讨了 Python 列表切片的基本概念和实际应用,通过具体示例展示了不同切片方式的使用方法及其背后的逻辑。 ... [详细]
author-avatar
w3812127
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有