将数字拆分为总和分量 [英] Split number into sum components

问题描述

有没有一种有效的算法将一个数字分成 N 个小节，这样数字的总和就等于原始数字，并有一个最小值?例如，如果我想将 50 分成 7 个小节，并且最小基数为 2，我可以执行 10,5,8,2,3,5,17(以及任何其他组合数).我想将数字保持为整数，并且相对随机，但我不确定如何有效地生成总计为原始数字并且不包括低于给定最小值的数字.有什么建议吗?

Is there an efficient algorithm to split up a number into N subsections so that the sum of the numbers adds up to the original, with a base minimum? For example, if I want to split 50 into 7 subsections, and have a base minimum of 2, I could do 10,5,8,2,3,5,17 (as well as any other number of combinations). I'd like to keep the numbers as integers, and relatively random but I'm not sure how to efficiently generate numbers that sum up to the original and don't include numbers lower than the given minimum. Any suggestions?

编辑 - 只是为了复制/粘贴我的评论，整数不必是唯一的，但我想避免所有整数的大小相同(例如，50 分成 10 个相同的大小).

EDIT - Just to copy/paste my comment, the integers don't have to be unique, but I want to avoid equal sizes for all of them (e.g. 50 split into 10 equal sizes) everytime.

推荐答案

这是一个算法:

1. 将 N 除以 m，其中 N 是您的编号，m 是小节数.李>
2. 将结果向下舍入到最接近的值，并将该值分配给所有小节.
3. 向每个小节添加一个，直到值加起来为 N.此时如果 N 为 50 而 m 为 7，则您将有 8, 7, 7, 7, 7, 7, 7
4. 从0迭代到m-1，步长为2，在-(currentValue-base)和currentValue-base.将该数字的倒数添加到其相邻存储桶中.如果您有奇数个存储桶，则在最后一个存储桶上，不要将该数字的倒数添加到其相邻存储桶中，而是以类似于上述第 2 步和第 3 步的分布式方式将其添加到所有其他存储桶中.

1. Divide N by m where N is your number and m is the number of subsections.
2. Round the result down to its nearest value and assign that value to all of the subsections.
3. Add one to each subsection until the values add up to N. At this point if N was 50 and m was 7, you'd have 8, 7, 7, 7, 7, 7, 7
4. Iterate from 0 to m-1, stepping by 2, and add a random number between -(currentValue-base) and currentValue-base. Add the inverse of that number to its neighboring bucket. If you have an odd number of buckets, then on the last bucket instead of adding the inverse of that number to its neighboring bucket, add it to all of the other buckets in a distributed manner similar to steps 2 and 3 above.

性能:第1步是O(1)，第2、3、4步是O(m)，所以总体是O(m).

Performance: Step 1 is O(1), Steps 2, 3, and 4 are O(m), so overall it's O(m).

这篇关于将数字拆分为总和分量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！