将数字拆分为总和部分

Question

是否有一种有效的算法将一个数字分成N个小部分，以便数字之和等于原始数字，并具有最小基数？例如，如果我想将 50 分成 7 个小节，并且最小基数为 2，我可以执行 10,5,8,2,3,5,17 （以及任何其他组合数）。我想将数字保留为整数，并且相对随机，但我不确定如何有效地生成总和等于原始值且不包含低于给定最小值的数字。有什么建议吗？

编辑-只是为了复制/粘贴我的评论，整数不必是唯一的，但我想避免每次都使用相同的大小（例如 50 分成 10 个相同大小）。

Answer 1

这是一个算法：

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

表现：
第 1 步的时间为 O(1)，步骤 2、3 和 4 的时间为 O(m)，因此总体来说为 O(m)。

Answer 2

您可以通过从数字中减去最小乘以 N、生成 N 个小节并添加最小值来轻松消除最小值的要求。在您的示例中，问题简化为将 36 拆分为 7 个整数，并且您给出了拆分 8,3,6,0,1,3,15。

解决方案的其余部分取决于“相对随机”要求的性质。对于一些最小的随机性，请考虑在 0 和未分割部分之间顺序选择数字（例如，首先在 0 和 36 之间，获得 8，然后在 0 和 28 之间，获得 3，依此类推 7 次）。如果这还不够，您需要首先定义随机性。

Answer 3

这是一个伪随机解决方案[请注意，解决方案可能有偏差，但相对随机]。

input:
n - the number we should sum up to
k - the number of 'parts'
m - minimum

(1) split n into k numbers: x1,x2,...,xk such that x1+...+xk = n, and the numbers 
    are closest possible to each other [in other words, x1 = x2 = ... = n/k where 
    possible, the end might vary at atmost +-1.]
(2) for each number xi from i=1 to k-1:
       temp <- rand(m,xi)
       spread x - temp evenly among xi+1,...,xk
       xi <- temp
(3) shuffle the resulting list.

对于第 1 部分，例如：对于 n=50, k = 7，您将设置：
x1=x2=...=x6=7,x7=8，用线性时间计算和填充这样的列表没有问题。

性能：

如上所述，step1 的复杂度为 O(k)。

步骤2，简单的实现是O(k^2)，但是由于你均匀地分配temp-xi的结果，所以有O(k)的实现，只需要存储和修改增量。

步骤 3 只是一个简单的洗牌，O(k)

总体性能：O(k)，并带有步骤 2 的增量实现

Answer 4

好吧，我想出了一些“只是为了好玩”的东西。

它从最小值逐渐增加到数字，并使用取模和随机的方式用N部分填充数组。

请参阅此处的 jsFiddle。

如果此数字的部分太多，它将无法按预期工作。 （即数字）

Answer 5

下面是创建所请求的数字重新分区的代码的 Java 示例。这是递归方法，我们将问题分解为 2 个子问题：如果我们想将一个数字分解为 n 个篮子中的分量之和，那么我们尝试一次考虑一个子数字，并为每个子问题委托找出答案剩余分解到 (n-1) 个篮子之间重新分配的递归调用。
处理特定子数时（在 for 循环中）会考虑请求的阈值。

import java.util.ArrayList;
import java.util.List;

public class TestFigures {

    public static List<List<Integer>> computeRepartitionNumber(int number_to_decompose, int number_of_subnumbers, int threshold_number) {
        List<List<Integer>> resultRec = new ArrayList<>();

        if (number_of_subnumbers == 1) {
            List<List<Integer>> resultEnd = new ArrayList<>();
            ArrayList<Integer> unitary = new ArrayList<>();
            resultEnd.add(unitary);
            unitary.add(number_to_decompose);
            return resultEnd;
        }

        for (int i = threshold_number; i <= number_to_decompose-threshold_number; i++) {
            int remain = number_to_decompose - i;
            List<List<Integer>> partialRec = computeRepartitionNumber(remain, number_of_subnumbers - 1, threshold_number);
            for(List<Integer> subList : partialRec){
                subList.add(i);             
            }
            resultRec.addAll(partialRec);
        }
        return resultRec;

    }

    public static void main(String[] args) {
        List<List<Integer>> superlist = computeRepartitionNumber(5, 2, 1);
        System.out.println(superlist.size());
        System.out.println(superlist);

    }

}

Answer 6

import random

def split_given_number_into_n_random_numbers(number, number_of_subsections, min_random_number_desired = 0):
    cumulative_sum_of_random_numbers = 0
    current_subsection = 1
    max_random_number = int(number/number_of_subsections)
    if min_random_number_desired > max_random_number:
        print("ERROR: Cannot have min number as {} and split {} in {} subsections".format(min_random_number_desired,
                                                                                          number, number_of_subsections))
        return False

    while (True):
        random_number = random.randint(min_random_number_desired, max_random_number)
        print("Random number {} = {}".format(current_subsection, random_number))
        cumulative_sum_of_random_numbers += random_number
        # print("Cumulative sum {}".format(sum_of_num))
        number -= random_number
        current_subsection += 1
        if current_subsection == number_of_subsections:
            random_number = number
            print("Random number {} = {}".format(current_subsection, random_number))
            cumulative_sum_of_random_numbers += random_number
            break

    print("Final cumulative sum of random numbers = {}".format(cumulative_sum_of_random_numbers))
    return True

if __name__ == '__main__':
    split_given_number_into_n_random_numbers(50, 7, 2)

现在，如果您希望最小数字为 2 以外的其他数字，请将其更改为提供的任何值 number_of_subsections * min_random_number_desired <= number。

Answer 7

让我用Python 来写它。

假设您有 50 个元素要分成 7 个框，并且每个框内至少需要两个元素。

N_init = 50
s = 2
m = 7

我们默认在每个框中放置 s 个元素，因此剩下 N 个元素。

N = N_init - s*m

我们随机抽取 m 个数字，对它们进行排序，然后在后面附加 N。这就像在一本 N 页的书中随机插入 m 个书签。
连续书签之间的页数是随机的。 （我们有 s，以便我们确定每个盒子至少有 s 个元素）

a = sorted([random.randint(0,N+1) for i in range(m)])
a.append(N)
a[0] = 0
result = [j-i+s for(i,j) in zip(a[0:m],a[1:m+1])]

完成！

Answer 8

这是一个 Ruby 实现。

def partition(num, components_length)
  temp = num
  arr = []
  # We generate a random number and substract it from num so the sum
  # of the elements of arr is always <= num.
  1.upto(components_length).each do
    rand = rand(1..temp) || 0
    temp -= rand
    arr << rand
  end

  return arr if arr.sum == num
  
  # if arr.sum is < num, we'll just add the difference to a random
  # element of arr. We could just use arr[0] if we want
  arr[arr.index(arr.sample)] += num - arr.sum

  # We can use arr.shuffle if we want more randomness
  arr
end

Answer 9

我知道已经有很长一段时间了，但我想添加我的答案来帮助某人，这里是我使用递归的代码

#include <stdio.h>
#include <stdlib.h>

void print(int n, int * a) {
int i ; 
for (i = 0; i <= n; i++) {
    printf("%d", a[i]); 
   i < n ? printf(" + ") : printf("");
}
printf("\n"); 
}

void integerPartition(int n, int * a, int level){
int first; 
int i; 
if (n < 1) return ;    
    a[level] = n;
print(level, a);
first = (level == 0) ? 1 : a[level-1];
for(i = first; i <= n / 2; i++){
    a[level] = i; 
    integerPartition(n - i, a, level + 1);
}
}
int main(int argc, char ** argv){
int n = 10;     
int * a = (int * ) malloc(sizeof(int) * n); 
integerPartition (n, a, 0); 
return(0);
}

这里 n 等于 10 但你可以像询问用户一样，通过使用声明 a 的大小新运营商！

Answer 10

我正在做类似的事情，这就是我的想法。

您可以在每一步使用一些计算以 O(N-1) 的速度完成此操作。首先，您在每个点的最小数和最大数之间选择一个随机数。对于每个点，最大数量是通过从剩余余额中减去 (Min_Number * Remaining_Spots) 来计算的。

例如：对于第一个位置，您选择一个 2 到 38 之间的数字。您可以通过从 50 中减去 (7-1)*2 来得到这个数字。即 50 - 12 = 38。

一旦您选择了一个数字，假设是 19，那么对于下一个位置的范围是 2-21。即 50-19-(5*2) = 21..

..等等。

这是代码片段：

function splitNumIntoXRandomComponents(num, x, min_num) {

var components = [];    

var count = 1;
var cumulative = 0;
var balance = num;

for (var i = 0; i<x-1; i++) {

    //max num for this spot
    var max_num = balance - ((x-count)*min_num);

    //to avoid big numbers in the beginning and min numbers at the end
    if (Math.random() > 0.5){ //0.5 can be tuned to your liking 
        max_num = Math.floor(max_num / 2) + min_num;
    }

    //generate the number for the spot at 'count'
    var c = Math.floor(Math.random()*(max_num-min_num+1)+min_num);

    //adjust balances
    cumulative += c;
    balance -= c;       
    count++;    

    //store this number
    components.push(c);                     

}

//push remaining balance into the last spot
components.push(balance);

//print numbers
console.log(components);

}

for (var i=0; i<10; i++) {
    splitNumIntoXRandomComponents(50, 7, 2);
}

这是示例输出：

[34, 2, 4, 3, 3, 2, 2]
[14, 12, 8, 8, 4, 2, 2]
[7, 4, 26, 5, 2, 3, 3]
[8, 2, 16, 4, 4, 9, 7]
[20, 8, 4, 4, 7, 4, 3]
[3, 34, 4, 2, 2, 2, 3]
[10, 5, 15, 2, 7, 5, 6]
[6, 3, 10, 4, 10, 3, 14]
[31, 4, 2, 3, 5, 2, 3]
[7, 5, 2, 9, 9, 2, 16]

这是 jsFiddle：
http://jsfiddle.net/wj81kvsc/6/