Split number into sum components

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 li开发者_StackOverflow中文版ke 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?

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.

---

Here's an algorithm:

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.

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

---

You can easily remove the requirement of a minimum by subtracting minimum times N from the number, generating the N subsections and adding the minimum. In your example, the problem reduces to splitting 36 into 7 integers, and you have given the split 8,3,6,0,1,3,15.

The rest of the solution depends on the nature of the "relatively random" requirement. For some minimal randomness, consider choosing numbers sequentially between 0 and the unsplitted part (e.g. between 0 and 36 first, gaining 8, then between 0 and 28, gaining 3, and so on 7 times). If that doesn't suffice, you'll need to define randomness first.

---

here is a pseudo random solution [note that solution might be biased, but will be relatively random].

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.

regarding part 1, for example: for n=50, k = 7, you will set: x1=x2=...=x6=7,x7=8, no problem to compute and populate such a list with linear time.

Performance:

As said, step1 is O(k).

Step2, with naive implementation is O(k^2), but since you distribute result of temp-xi evenly, there is O(k) implementation, with just storing and modifying delta.

Step3 is just a simple shuffle, O(k)

Overall performance: O(k) with delta implemntation of step2

---

Well I've come up with something "just for fun".

It goes incrementally from minimum to number and populates an array with N sections using modulo and random.

See the jsFiddle here.

It won't work as expected if there are too many sections for this number. (ie number < N(N+1)/2)

---

Here is a java example of code creating the requested repartition of numbers. It is recursive approach, we decompose the problem into 2 subproblems : if we want to decompose a number in to a sum of components amongst n baskets, then we try to consider a subnumber at a time, and for each of them delegate the finding out of the remaining decomposition to the recursive call for the repartition amongst (n-1) baskets. The requested threshold is considered when processing a particular subnumber (in the for loop).

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);

    }

}

---

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)

Now if you want minimum number to be something else besides 2, change it to any value provided number_of_subsections * min_random_number_desired <= number.

---

Let me write it in Python.

Let's say that you have 50 elements to split into 7 boxes and you want at least two inside each of them.

N_init = 50
s = 2
m = 7

We put s elements by default in each box so we are left with N elements.

N = N_init - s*m

We draw m random numbers, sort them, append N on the back. This is like inserting randomly m bookmarks in a book of N pages. The number of pages between consecutive bookmarks is random. (We had s so that we are sure that each box has at least s elements)

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])]

Done!

---

I know there`s been a long time but i would like to add my answer to help someone here is my code using recursion

#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);
}

Here n is equal to 10 but u could make it like asking the user,declare the size of a by using the new operator !

---

I was working on something similar and here is what I came up with.

You can do this in O(N-1) using some calculations at each step. You begin by picking a random number between the minimum number and max number for each spot. For each spot, max number is calculated by subtracting (Min_Number * Remaining_Spots) from the Remaining Balance.

For example: for the first spot you pick a number between 2 and 38. You get this by subtracting (7-1)*2 from 50. i.e. 50 - 12 = 38.

Once you pick a number, let's say 19, then for the next spot the range is 2-21. i.e. 50-19-(5*2) = 21..

..and so on.

Here is the code snippet:

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);
}

Here is the sample output:

[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]

Here is the jsFiddle: http://jsfiddle.net/wj81kvsc/6/

---

Here is a Ruby implementation.

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