Divide a number N into K numbers
21 views (last 30 days)
Show older comments
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.
2 Comments
Accepted Answer
John D'Errico
on 6 Mar 2021
Edited: John D'Errico
on 6 Mar 2021
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.
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.
More Answers (2)
Image Analyst
on 6 Mar 2021
randfixedsum():
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.
0 Comments
Image Analyst
on 6 Mar 2021
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
0 Comments
See Also
Categories
Find more on Creating and Concatenating Matrices in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!