Divide a number N into K numbers

How to divide a number into the sum of many numbers. For example, 64 is divided into the sum of eight numbers, each of which is not less than 1 and not more than 16.

[dpb]

Must they be integral? May they be repeated?

[Stephen23]

dpb: integral -> integer ?

Interestingly the question does not actually mention integer anywhere.

Answer 1

[John D'Errico]

The dissection of an integer into a sum of integers is called an integer partition.

Assuming these are integers in the sum, then it is easy, within limits. A problem is, there are MANY ways to dissect that total into a sum of parts, at least if replicates are allowed. I'll show how to solve the problem in general, with replicates allowed or not.

You need to download my partitions function from the file exchange.

First, if no replacement is allowed, then there are 486 possible ways to write that sum.

X = partitions(64,1:16,1,8);
>> size(X,1)
ans =
   486

This generates the complete list of every possible such dissection of the number 64. Each row of X corresponds to one of them. Here are four of them, chosen arbitrarily. X is an array that tells you if the indicated element is present in the sum, and how many times it appears.

>> X(1,:)
ans =
     0     0     0     1     1     1     1     0     1     1     1     1     0     0     0     0

We can use find to extract the elements of that sum.

>> find(X(1,:))
ans =
     4     5     6     7     9    10    11    12
>> find(X(2,:))
ans =
     3     5     6     8     9    10    11    12
>> find(X(3,:))
ans =
     3     4     7     8     9    10    11    12
     
>> find(X(486,:))
ans =
     1     2     3     4     9    14    15    16

How would you use this to pick a random sample that sums to 64 under these conditions? Just pick out a random row of X.

>> find(X(randi(486,1),:))
ans =
     2     3     7     8     9    10    11    14

If replicates are allowed, so you are sampling with replacement from the numbers 1:16, the problem grows large quickly.

>> X = partitions(64,1:16,[],8);
>> size(X,1)
ans =
       11975

So there are 11975 possible ways to dissect the number 64 into a sum of exactly 8 integers from the set 1:16, IF replication is allowed. One of those solutions is just 8 replicates of the number 8.

>> X(1,:)
ans =
     0     0     0     0     0     0     0     8     0     0     0     0     0     0     0     0

Here is a random set, where the number 10 appeared twice.

>> X(randi(11975,1),:)
ans =
     0     0     0     1     1     1     1     1     0     2     0     0     0     1     0     0

You can find partitions on the file exchange, for free download.

https://www.mathworks.com/matlabcentral/fileexchange/12009-partitions-of-an-integer

Finally, remember that if the total sum if large, and the set of elements in that sum may be large, then the number of possible partitions can be HUGE.

[chen jiyuan]

thanks a lot

Answer 2

[Image Analyst]

randfixedsum():

https://www.mathworks.com/matlabcentral/fileexchange/9700-random-vectors-with-fixed-sum?s_tid=srchtitle

This generates m random n-element column vectors of values, [x1;x2;...;xn], each with a fixed sum, s, and subject to a restriction a<=xi<=b. The vectors are randomly and uniformly distributed in the n-1 dimensional space of solutions. This is accomplished by decomposing that space into a number of different types of simplexes (the many-dimensional generalizations of line segments, triangles, and tetrahedra.) The 'rand' function is used to distribute vectors within each simplex uniformly, and further calls on 'rand' serve to select different types of simplexes with probabilities proportional to their respective n-1 dimensional volumes. This algorithm does not perform any rejection of solutions - all are generated so as to already fit within the prescribed hypercube.

Cite As

Roger Stafford (2021). Random Vectors with Fixed Sum (https://www.mathworks.com/matlabcentral/fileexchange/9700-random-vectors-with-fixed-sum), MATLAB Central File Exchange. Retrieved March 6, 2021.

Answer 3

[Image Analyst]

Here's one way. (Hopefully it's not your homework. Tag it as homework if it is.)

N = 8;
r = 1 + 15 * rand(10000, N)
% Compute sum of each row
theSums = sum(r, 2)
% Find sums more than 64
index64 = theSums >= 64;
% Set below 64 to infinity
theSums(~index64) = inf;
% Find the one closest to 64:
[value, index] = min(theSums)
% Extract those N numbers
theEightNumbers = r(index, :)
% Rescale so the sum is exactly 64
theEightNumbers = theEightNumbers * 64 / sum(theEightNumbers)
% Double Check
sum(theEightNumbers)

You'll see

theEightNumbers =

6.1735 2.1348 10.4723 1.6452 14.5796 5.4155 12.5308 11.0483

ans =

64