- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
我想生成一个字典序列的数字,这样每个数字的数字总和就是一个给定的常量。它有点类似于“子集和问题”。例如,如果我希望生成 sum = 3 的 4 位数字,那么我有一个类似的系列:
[3 0 0 0]
[2 1 0 0]
[2 0 1 0]
[2 0 0 1]
[1 2 0 0] ...等等。
我能够使用以下代码在 Python 中成功完成:
import numpy as np
M = 4 # No. of digits
N = 3 # Target sum
a = np.zeros((1,M), int)
b = np.zeros((1,M), int)
a[0][0] = N
jj = 0
while a[jj][M-1] != N:
ii = M-2
while a[jj][ii] == 0:
ii = ii-1
kk = ii
if kk > 0:
b[0][0:kk-1] = a[jj][0:kk-1]
b[0][kk] = a[jj][kk]-1
b[0][kk+1] = N - sum(b[0][0:kk+1])
b[0][kk+2:] = 0
a = np.concatenate((a,b), axis=0)
jj += 1
for ii in range(0,len(a)):
print a[ii]
print len(a)
我认为这不是一种非常有效的方法(因为我是 Python 新手)。它适用于较小的 M 和 N (<10) 值,但超过此值就非常慢。我希望将它用于 M ~ 100 和 N ~ 6。我怎样才能使我的代码更高效或者是否有更好的编码方式?
最佳答案
改编自 Jorg Arndt 的书“Matters Computational”的非常有效的算法
(第 7.2 部分的组合字典顺序
)
n = 4
k = 3
x = [0] * n
x[0] = k
while True:
print(x)
v = x[-1]
if (k==v ):
break
x[-1] = 0
j = -2
while (0==x[j]):
j -= 1
x[j] -= 1
x[j+1] = 1 + v
[3, 0, 0, 0]
[2, 1, 0, 0]
[2, 0, 1, 0]
[2, 0, 0, 1]
[1, 2, 0, 0]
[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 2, 0]
[1, 0, 1, 1]
[1, 0, 0, 2]
[0, 3, 0, 0]
[0, 2, 1, 0]
[0, 2, 0, 1]
[0, 1, 2, 0]
[0, 1, 1, 1]
[0, 1, 0, 2]
[0, 0, 3, 0]
[0, 0, 2, 1]
[0, 0, 1, 2]
[0, 0, 0, 3]
n=100 和 k = 2,3,4,5 (2.8 ghz Cel-1840) 的纯 Python(也许 numpy 数组更快)的组合数和秒数
2 5050 0.040000200271606445
3 171700 0.9900014400482178
4 4421275 20.02204465866089
5 91962520 372.03577995300293
I expect time 2 hours for 100/6 generation
与 numpy 数组相同 (x = np.zeros((n,), dtype=int)
) 给出更差的结果 - 但也许是因为我不知道如何正确使用它们
2 5050 0.07999992370605469
3 171700 2.390003204345703
4 4421275 54.74532389640808
native 代码(这是 Delphi,C/C++ 编译器可能优化得更好)生成 100/6 在 21 秒内
3 171700 0.012
4 4421275 0.125
5 91962520 1.544
6 1609344100 20.748
在所有测量都没有完成之前无法休眠:)
MSVS VC++:18 秒! (O2优化)
5 91962520 1.466
6 1609344100 18.283
所以每秒有 1 亿个变体。大量时间浪费在检查空单元格上(因为填充率很小)。 Arndt 描述的速度是在更高的 k/n 比率下达到的,大约每秒 300-5 亿个变体:
n=25, k=15 25140840660 60.981 400 millions per second
关于python - 在 Python 中高效地生成词典系列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55258576/
我正在尝试这样做: var myBeacons: [NSUUID: [Int]] = [NSUUID(UUIDString:"74278BDA-B644-4520-8F0C-720EAF059935"
我的字典有问题。如果我将一个对象添加到字典中,它会用添加的项目覆盖整个包含项目。 添加所有元素后,Dictionary 包含正确数量的项目,但项目都是最后添加的项目。 For Each shp In
我使用字典,我将有大约一百万个条目,我将定期添加、删除、编辑和轮询..我想知道所有条目的上/下边是什么,如果有一种更高效的方式。 最佳答案 这取决于你想做什么。如果您想要一个具有快速插入、查找和删除功
我在 Swift 类中的字典数组方面遇到问题。我的代码无法在类或结构中运行,但可以在外部运行。 var data = [Dictionary]() data.append([123: "test"])
有没有一种方法可以添加注释来记录 Dictionary 或 ConcurrentDictionary 以了解键/值的含义? 例如: Dictionary _users; 这个例子有一个用户字典。 gu
我正在基于 Android AOSP LatinIME 项目创建自己的输入法应用。我设法找到了一些用于自动更正和预测的字典文件(main_en.dict、main_fr.dict 等)。 但对于许多其
我已经通过 Locale::Maketext 使我的网站支持多种语言(或更具体地说是 CatalystX::I18N::Model::Maketext )。 我的 maketext 类在编译时通过从数
我不会说英语,而且我的英语也不是很好。我自以为是。我没有和其他人一起在一个共同的代码库上工作过。我没有任何编程的 friend 。我不与其他程序员一起工作(至少没有人关心这些事情)。 我想这可能解释了
我需要做 currentKey+1。所以我想找到键值的索引并获取下一个键(如果在末尾则为第一个)。我如何找到 key 的当前索引? 我正在使用 Dictionary我用 Linq 查找 .Find 或
关闭。这个问题需要details or clarity .它目前不接受答案。 想改进这个问题吗? 通过 editing this post 添加细节并澄清问题. 关闭 9 年前。 Improve t
我使用 python 2.7 中的 shelve 模块保存了一个数据文件,该文件不知何故已损坏。我可以用 db = shelve.open('file.db') 加载它,但是当我调用 len(db)
我想试试这个抽认卡的想法,为即将到来的测试尝试学习关键字及其含义。我想在 python 上创建一个字典,我可以用它来帮助解决这个问题。这个想法是向我显示定义,然后我必须猜测已定义的词。我在下面展示了如
当尝试 .format() 一次列表中的多个词典时,控制台会给我一个 AttributeError:'list' object has no attribute 'items'。 我尝试滚动浏览提示的
我在公共(public)类(class)中有一个公共(public)词典如下: namespace ApiAssembly { public static class TypeStore
我需要做 currentKey+1。所以我想找到键值的索引并获取下一个键(如果在末尾则为第一个)。我如何找到 key 的当前索引? 我正在使用 Dictionary我用 Linq 查找 .Find 或
我的字典总是零,想了解为什么会这样。我的代码: var dic = [NSDate : MCACalendar]?() dic?[currentDate!] = calendar 最佳答案 @Kirs
给定(简化描述) 我们的一项服务在内存中有很多实例。大约 85% 是独一无二的。我们需要对这些项目进行非常快速的基于键的访问,因为它们在单个堆栈/调用中被非常频繁查询。这个单一上下文的性能得到了极大的
我想为“Sinhala Language speech recognition”僧伽罗语建立新的声学模型、新词典、新语言模型字符是基于 Unicode 的。例如 A=අ,I=ඉ,U=උ,KA=ක,BA
我需要一个带有 的正面和负面词的列表重量 根据单词的强度和周数分配单词。我有 : 1.) WordNet - 它为每个单词提供 + 或 - 分数。 2.) SentiWordNet - 在 [0,1]
我有一个 Jinja2 字典,我想要一个可以修改它的表达式 - 通过更改其内容或与另一个字典合并。 >>> import jinja2 >>> e = jinja2.Environment() 修改字
我是一名优秀的程序员,十分优秀!