Split number into sum components

Question

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?

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.

Answer 1

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

Answer 2

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.