Divide a number N into K numbers
20 次查看(过去 30 天)
显示 更早的评论
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 个评论
采纳的回答
John D'Errico
2021-3-6
编辑:John D'Errico
2021-3-6
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.
更多回答(2 个)
Image Analyst
2021-3-6
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 个评论
Image Analyst
2021-3-6
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 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!